Se proporciona una expresión que contiene $N$ variables booleanas. Escribe un programa que calcule el número de formas de asignar valores a las variables tales que el valor de la expresión sea 0, considerando los $2^N$ casos posibles.

En este problema, una expresión válida se define mediante la siguiente notación BNF:

• boolean ::= '0' | '1'
• variable ::= 'a' | 'b' | ... | $N$-ésima letra minúscula del alfabeto
• value ::= boolean | variable
• condition ::= value '==' value
• expression ::= value | condition '?' expression ':' expression

El valor de la expresión se denota como eval(expression) y se calcula de forma recursiva como se muestra a continuación. Al analizarlo, se puede observar que, dada una expresión válida, la forma de calcularla es única.

• eval(value) = value
• eval(condition) = eval(value1 '==' value2) = $$\begin{cases} 1 & \text{si } eval(value1) = eval(value2) \\ 0 & \text{en otro caso} \end{cases}$$
• eval(expression) = eval(value) = value
• eval(expression) = eval(condition '?' expression1 ':' expression2) = $$\begin{cases} eval(expression1) & \text{si } eval(condition) = 1 \\ eval(expression2) & \text{en otro caso} \end{cases}$$

Entrada

La primera línea contiene el número de variables $N$ ($1 \le N \le 26$). La segunda línea contiene una cadena de caracteres de longitud entre 1 y 1000 que representa la expresión. La expresión solo contiene los caracteres '0', '1', 'a'–($N$-ésima letra minúscula del alfabeto), '=', '?', ':' y siempre será una expresión válida.

Salida

Imprime el número de formas de asignar valores a las variables para que el valor de la expresión sea 0.

Ejemplos

Entrada 1

2
a==b?a:0

Salida 1

3

Entrada 2

10
0

Salida 2

1024