Forgetful Zenyk

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Forgetful Zenyk is a rich programmer. Zenyk values his huge salary and stores it in two different banks (we will not mention the names of these banks, as they did not pay us for advertising). Accordingly, Zenyk has two bank cards. The PIN code for each card contains exactly \(n\) digits, each of which is 0 or 1. To avoid forgetting the PIN codes, because storing written PIN codes is very reckless, Zenyk decided to write down a string \(x\) of digits 0 and 1, for which he performed the following operation: string \(x\) contains 1 only in the positions where the digits in his passwords differ and 0 otherwise.

Zenyk knows that if he forgets one of the PIN codes, he will be able to restore the forgotten one using the string \(x\) and the other PIN code. But alas, he forgot both PIN codes. Zenyk got incredibly upset and even cried a little. Realizing that tears will not return his wealth, he decided to iterate over all possible pairs of PIN codes that produce the string \(x\) after performing the corresponding operation. Tell Zenyk how many pairs of PIN codes he will need to check.

Input

The first line contains a single integer \(n\) and a string \(x\) — the length of the PIN codes and the result of the operation for the passwords, respectively.

Output

In a single line, output the number of pairs of PIN codes that have length \(n\) and produce the string \(x\) as a result of the operation.

Constraints

\(1 \le n = |x| \le 30\),

where \(|x|\) is the length of the string \(x\),

the string \(x\) contains only digits 0 and 1,

Problem evaluation consists of the following blocks:

1 point each — examples from the statement,

8 points — a block of tests in which \(n \le 10\),

10 points — a block of tests in which \(n \le 20\),

5 points — a block of tests in which \(n \le 30\),

Points for a block will be awarded only if you give the correct answer to all tests in the block.

Samples

Input (stdin) сopy	Output (stdout) сopy
2 10	4

Input (stdin) сopy	Output (stdout) сopy
4 0111	16

Notes

Pairs that satisfy the first example: (01, 11), (11, 01), (00, 10), (10, 00).