# Problem D

Extensive Or

Consider a very large number $R$ in a compressed format. It is compressed as a binary string $s$, and an integer $k$. Start with the empty string, and append $s$ to it $k$ times to get the binary representation of $R$. The string $s$ is guaranteed to have a leading $1$. Now, with $R$, solve the following problem: How many sets of $n$ distinct integers are there such that each integer is between 0 and $R-1$, inclusive, and the XOR of all those integers is equal to zero? Since this number can get very large, return it modulo $10^{9}+7$.

As a reminder, XOR is Exclusive Or. The XOR of two numbers is done bitwise. Using $\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

Each input will consist of a single test case. Note that
your program may be run multiple times on different inputs.
Each input consists of exactly two lines. The first line has
two space-separated integers $n$ ($3\le n \le 7$) and $k$ ($1
\le k \le 100\, 000$), where $n$ is the number of distinct integers
in the sets, and $k$ is
the number of times to repeat the string $s$ in order to build $R$. The second line contains only the
string $s$, which will
consist of at least 1 and at most 50 characters, each of which
is either `0` or `1`. $s$ is
guaranteed to begin with a `1`.

## Output

Output a single line with a single integer, indicating the number of sets of $n$ distinct integers that can be formed, where each integer is between 0 and $R-1$ inclusive, and the XOR of the $n$ integers in each set is 0. Output this number modulo $10^9+7$.

Sample Input 1 | Sample Output 1 |
---|---|

3 1 100 |
1 |

Sample Input 2 | Sample Output 2 |
---|---|

4 3 10 |
1978 |

Sample Input 3 | Sample Output 3 |
---|---|

5 100 1 |
598192244 |