题目描述

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:

$$\begin{aligned} 0 \oplus 0 &= 0 \\ 0 \oplus 1 &= 1 \\ 1 \oplus 0 &= 1 \\ 1 \oplus 1 &= 0 \\ \end{aligned}$$

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

输入格式

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 \leq n \leq 7$) and $k$ ($1 \leq k \leq 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 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