You are given an expression containing $N$ boolean variables. Write a program to calculate the number of ways to assign values to these variables such that the value of the expression is $0$, out of the $2^N$ possible assignments.

In this problem, a valid expression is defined by the following BNF notation:

• boolean ::= '0' | '1'
• variable ::= 'a' | 'b' | ... | $N$-th lowercase alphabet letter
• value ::= boolean | variable
• condition ::= value '==' value
• expression ::= value | condition '?' expression ':' expression

The value of an expression is denoted by $eval(expression)$ and is calculated recursively as follows. It can be observed that for any given valid expression, there is a unique way to evaluate it.

• $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}$

Input

The first line contains the number of variables $N$ ($1 \le N \le 26$). The second line contains a string representing the expression, with a length between $1$ and $1\,000$ inclusive. The expression consists only of '0', '1', 'a' through the $N$-th lowercase alphabet letter, '=', '?', and ':', and is guaranteed to be a valid expression.

Output

Output the number of ways to assign values to the variables such that the value of the expression is $0$.

Examples

Input 1

2
a==b?a:0

Output 1

3

Input 2

10
0

Output 2

1024