$N$ 個の真偽値変数を持つ式が与えられる。変数の値として可能な $2^N$ 通りの組み合わせについて、式の値が $0$ になるような組み合わせの数を求めるプログラムを作成せよ。

この問題において、正しい式とは以下の BNF 表記法における expression を指す。

• 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 \text{ '==' } value2) = \begin{cases} 1 & \text{if } eval(value1) = eval(value2) \\ 0 & \text{otherwise} \end{cases}$
• $eval(expression) = eval(value) = value$
• $eval(expression) = eval(condition \text{ '?' } expression1 \text{ ':' } expression2) = \begin{cases} eval(expression1) & \text{if } eval(condition) = 1 \\ eval(expression2) & \text{otherwise} \end{cases}$

入力

1 行目には変数の数 $N$ ($1 \le N \le 26$) が与えられる。 2 行目には式に該当する長さ $1$ 以上 $1\,000$ 以下の文字列が与えられる。式は '0', '1', 'a' から ($N$ 番目の小文字アルファベット), '=', '?', ':' のみで構成され、正しい式のみが与えられる。

出力

式の値が $0$ になるような変数の値の割り当て方の数を出力せよ。

入出力例

入力 1

2
a==b?a:0

出力 1

3

入力 2

10
0

出力 2

1024