Extensive Or

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$.

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.

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$.