給定一個包含 $N$ 個布林變數的運算式。請撰寫一個程式，計算在變數所有可能的 $2^N$ 種賦值情況下，運算式的值為 $0$ 的次數。

在本題中，合法的運算式由以下 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{if } eval(value1) = eval(value2) \\ 0 & \text{otherwise} \end{cases} $$
• eval(expression) = eval(value) = value
• eval(expression) = eval(condition '?' expression1 ':' expression2) = $$ \begin{cases} eval(expression1) & \text{if } eval(condition) = 1 \\ eval(expression2) & \text{otherwise} \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