Cho một biểu thức chứa $N$ biến đúng/sai. Hãy viết chương trình tính số cách gán giá trị cho các biến sao cho giá trị của biểu thức bằng 0, xét trên tất cả $2^N$ trường hợp có thể xảy ra của các biến.

Trong bài toán này, một biểu thức hợp lệ được định nghĩa theo ký pháp BNF cho expression như sau:

• boolean ::= '0' | '1'
• variable ::= 'a' | 'b' | ... | chữ cái thường thứ $N$
• value ::= boolean | variable
• condition ::= value '==' value
• expression ::= value | condition '?' expression ':' expression

Giá trị của biểu thức được ký hiệu là $eval(expression)$ và được tính toán đệ quy như sau. Có thể thấy rằng với một biểu thức hợp lệ, cách tính toán giá trị của biểu thức đó là duy nhất.

• $eval(value) = value$
• $eval(condition) = eval(value_1 \text{ '==' } value_2) = \begin{cases} 1 & \text{nếu } eval(value_1) = eval(value_2) \\ 0 & \text{trường hợp khác} \end{cases}$
• $eval(expression) = eval(value) = value$
• $eval(expression) = eval(condition \text{ '?' } expression_1 \text{ ':' } expression_2) = \begin{cases} eval(expression_1) & \text{nếu } eval(condition) = 1 \\ eval(expression_2) & \text{trường hợp khác} \end{cases}$

Dữ liệu vào

Dòng đầu tiên chứa số lượng biến $N$ ($1 \le N \le 26$). Dòng thứ hai chứa một chuỗi ký tự có độ dài từ 1 đến 1000 đại diện cho biểu thức. Biểu thức chỉ bao gồm các ký tự '0', '1', 'a'–(chữ cái thường thứ $N$), '=', '?', ':' và luôn là một biểu thức hợp lệ.

Dữ liệu ra

In ra số cách gán giá trị cho các biến để giá trị của biểu thức bằng 0.

Ví dụ

Dữ liệu vào 1

2
a==b?a:0

Dữ liệu ra 1

3

Dữ liệu vào 2

10
0

Dữ liệu ra 2

1024