Дано выражение, содержащее $N$ булевых переменных. Напишите программу, которая вычисляет количество способов присвоить значения переменным так, чтобы значение выражения было равно 0. Всего существует $2^N$ возможных комбинаций значений переменных.

В этой задаче корректное выражение определяется согласно следующей нотации 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(value1 '==' value2) = $\begin{cases} 1 & \text{если } eval(value1) = eval(value2) \\ 0 & \text{в противном случае} \end{cases}$
• eval(expression) = eval(value) = value
• eval(expression) = eval(condition '?' expression1 ':' expression2) = $\begin{cases} eval(expression1) & \text{если } eval(condition) = 1 \\ eval(expression2) & \text{в противном случае} \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