On vous donne une expression contenant $N$ variables booléennes. Écrivez un programme qui calcule le nombre de façons d'assigner des valeurs aux variables de sorte que la valeur de l'expression soit $0$, parmi les $2^N$ combinaisons possibles.

Dans ce problème, une expression valide est définie par la notation BNF suivante :

• boolean ::= '0' | '1'
• variable ::= 'a' | 'b' | ... | $N$-ième lettre minuscule de l'alphabet
• value ::= boolean | variable
• condition ::= value '==' value
• expression ::= value | condition '?' expression ':' expression

La valeur de l'expression est donnée par $eval(expression)$ et est calculée récursivement comme suit. En y réfléchissant bien, on peut constater que pour une expression valide donnée, la méthode de calcul est unique.

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

Entrée

La première ligne contient le nombre de variables $N$ ($1 \le N \le 26$). La deuxième ligne contient une chaîne de caractères de longueur comprise entre $1$ et $1\,000$ représentant l'expression. L'expression est composée uniquement de '0', '1', 'a'–($N$-ième lettre minuscule de l'alphabet), '=', '?', et ':', et seule une expression valide est donnée.

Sortie

Affichez le nombre de façons d'assigner des valeurs aux variables pour que la valeur de l'expression soit $0$.

Exemples

Entrée 1

2
a==b?a:0

Sortie 1

3

Entrée 2

10
0

Sortie 2

1024