Extensive Or

Time limit3sMemory limit256 MB

Summary

Count n-element subsets of numbers below the huge binary bound formed by repeating s k times whose xor is zero, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Bit manipulation
Solved: No attempts yet

Problem

A very large number $R$ is given in compressed form. The compression is a binary string $s$ and an integer $k$ . Start from the empty string and append $s$ to it $k$ times to get the binary representation of $R$ . The first character of $s$ is always 1.

For that $R$ , answer the following. How many sets of $n$ distinct integers are there such that every element is between 0 and $R - 1$ inclusive and the XOR of all elements is 0? The count can get very large, so report it modulo $10^9 + 7$ .

XOR is exclusive or, and the XOR of two numbers is taken bit by bit. Writing $\oplus$ for XOR:

$0 \oplus 0 = 0$
$0 \oplus 1 = 1$
$1 \oplus 0 = 1$
$1 \oplus 1 = 0$

XOR is associative, so $a \oplus (b \oplus c) = (a \oplus b) \oplus c$ .

Input

The input is a single test case and has exactly two lines. The first line has two space separated integers $n$ and $k$ ( $3 \le n \le 7$ , $1 \le k \le 100000$ ), where $n$ is the number of distinct integers in a set and $k$ is how many times $s$ is repeated to build $R$ . The second line has the string $s$ . Its length is between 1 and 50, every character is 0 or 1, and the first character is 1.

Output

Print on one line the number of sets of $n$ distinct integers, each between 0 and $R - 1$ inclusive, whose elements XOR to 0, modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
3 1
100
```
Expected output
```
1
```
Example 2
Input
```
4 3
10
```
Expected output
```
1978
```
Example 3
Input
```
5 100
1
```
Expected output
```
598192244
```