给定一个包含 $N$ 个布尔变量的表达式。请编写一个程序，计算在 $2^N$ 种可能的变量赋值情况下，表达式的值为 $0$ 的方案数。

在本题中，合法的表达式由以下 BNF 范式定义：

• boolean ::= '0' | '1'
• variable ::= 'a' | 'b' | ... | 第 N 个小写字母
• value ::= boolean | variable
• condition ::= value '==' value
• expression ::= value | condition '?' expression ':' expression

表达式的值由 $eval(expression)$ 定义，并按如下方式递归计算。可以发现，对于给定的合法表达式，其计算方式是唯一的。

• $eval(value) = value$
• $eval(condition) = eval(value_1 \text{ '==' } value_2) = \begin{cases} 1 & \text{if } eval(value_1) = eval(value_2) \\ 0 & \text{otherwise} \end{cases}$
• $eval(expression) = eval(value) = value$
• $eval(expression) = eval(condition \text{ '?' } expression_1 \text{ ':' } expression_2) = \begin{cases} eval(expression_1) & \text{if } eval(condition) = 1 \\ eval(expression_2) & \text{otherwise} \end{cases}$

输入格式

第一行包含变量的数量 $N$ ($1 \le N \le 26$)。

第二行包含一个长度在 $1$ 到 $1000$ 之间的字符串，表示该表达式。表达式仅由字符 '0', '1', 'a' 到第 $N$ 个小写字母, '=', '?', ':' 组成，且保证给出的表达式合法。

输出格式

输出使得表达式的值为 $0$ 的变量赋值方案数。

样例

样例输入 1

2
a==b?a:0

样例输出 1

3

样例输入 2

10
0

样例输出 2

1024