A binary string s of length N = 2ⁿ is given. You will perform the following operation n times :

- Choose one of the operators AND (&), OR (|) or XOR (^). Suppose the current string is S = s₁s₂...s_k. Then, for all , replace s_2i-1s_2i with the result obtained by applying the operator to s_2i-1 and s_2i. For example, if we apply XOR to {1101} we get {01}.

After n operations, the string will have length 1.

There are 3ⁿ ways to choose the n operations in total. How many of these ways will give 1 as the only character of the final string.

The first line of input contains a single integer n (1 ≤ n ≤ 18).

The next line of input contains a single binary string s (|s| = 2n). All characters of s are either 0 or 1.

Output a single integer, the answer to the problem.

2
1001

4

The sequences (XOR, OR), (XOR, AND), (OR, OR), (OR, AND) works.