Dane jest wyrażenie zawierające $N$ zmiennych logicznych (prawda/fałsz). Napisz program, który obliczy, dla ilu spośród $2^N$ możliwych przypisań wartości zmiennym, wartość całego wyrażenia wynosi 0.

W tym zadaniu poprawne wyrażenie jest zdefiniowane zgodnie z poniższą notacją BNF dla expression:

• boolean ::= '0' | '1'
• variable ::= 'a' | 'b' | ... | N-ta mała litera alfabetu
• value ::= boolean | variable
• condition ::= value '==' value
• expression ::= value | condition '?' expression ':' expression

Wartość wyrażenia to eval(expression), obliczana rekurencyjnie w następujący sposób. Można zauważyć, że dla poprawnego wyrażenia sposób jego obliczenia jest jednoznaczny.

• eval(value) = value
• eval(condition) = eval(value1 '==' value2) = $$\begin{cases} 1 & \text{jeśli } eval(value1) = eval(value2) \\ 0 & \text{w przeciwnym razie} \end{cases}$$
• eval(expression) = eval(value) = value
• eval(expression) = eval(condition '?' expression1 ':' expression2) = $$\begin{cases} eval(expression1) & \text{jeśli } eval(condition) = 1 \\ eval(expression2) & \text{w przeciwnym razie} \end{cases}$$

Wejście

W pierwszej linii podana jest liczba zmiennych $N$ ($1 \le N \le 26$). W drugiej linii podany jest ciąg znaków o długości od 1 do 1000, reprezentujący wyrażenie. Wyrażenie składa się wyłącznie ze znaków '0', '1', 'a'–(N-ta mała litera alfabetu), '=', '?', ':' i jest zawsze poprawnym wyrażeniem.

Wyjście

Wypisz liczbę sposobów przypisania wartości zmiennym tak, aby wartość wyrażenia wynosiła 0.

Przykład

Wejście 1

2
a==b?a:0

Wyjście 1

3

Wejście 2

10
0

Wyjście 2

1024