题目描述

给定一个含有 $N$ 个布尔变量的表达式。

对于变量的全部 $2^N$ 种取值方式，求表达式值为 $0$ 的取值方式数量。

本题中的合法表达式由下面的 BNF 文法定义：

boolean    ::= '0' | '1'
variable   ::= 'a' | 'b' | ... | 第 N 个小写英文字母
value      ::= boolean | variable
condition  ::= value '==' value
expression ::= value | condition '?' expression ':' expression

表达式的值记为 $\operatorname{eval}(\text{expression})$，并按如下规则递归计算。

对于一个值：

$$\operatorname{eval}(\text{value})=\text{value}.$$

对于一个条件：

$$\operatorname{eval}(\text{value}_1==\text{value}_2)= \begin{cases} 1,&\operatorname{eval}(\text{value}_1)=\operatorname{eval}(\text{value}_2),\\ 0,&\text{否则}. \end{cases}$$

对于一个三元表达式：

$$\operatorname{eval}(\text{condition}?\text{expression}_1:\text{expression}_2)= \begin{cases} \operatorname{eval}(\text{expression}_1),&\operatorname{eval}(\text{condition})=1,\\ \operatorname{eval}(\text{expression}_2),&\text{否则}. \end{cases}$$

可以证明，对任意合法表达式，其解析和计算方式都是唯一的。

输入格式

第一行包含变量数量 $N$。

第二行包含一个表示表达式的字符串。

字符串只会包含：

• 0、1；
• 从 a 开始的前 $N$ 个小写英文字母；
• =、?、:。

保证输入字符串是合法表达式。

输出格式

输出使表达式值等于 $0$ 的变量赋值方案数。

数据范围

$$1\le N\le 26,$$

表达式字符串长度满足

$$1\le |S|\le 1000.$$

样例 1

输入

2
a==b?a:0

输出

3

样例 2

输入

10
0

输出

1024