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:

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

3 1
100

1

4 3
10

1978

5 100
1

598192244