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 100000$), 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$.

-----Examples-----
Sample Input 1:
3 1
100
Sample Output 1:
1

Sample Input 2:
4 3
10
Sample Output 2:
1978

Source: kattis | Difficulty: MEDIUM


Solutions: