Description

JYY has recently been studying bitwise operations. He found that the most interesting one is the xor operation. For the xor of two numbers, JYY discovered a fact: the xor of two numbers is $0$ if and only if they are equal. Then JYY started thinking: what properties does the xor of $N$ numbers have?

JYY wants to know: within the range from $0$ to $R-1$, choose $N$ distinct integers such that the xor of these $N$ integers is $0$. How many different ways are there to choose them? (Different selection orders are not counted multiple times; see the sample.)

JYY is a computer scientist, so the $R$ in his mind is extremely large. To describe it conveniently, if we write $R$ as a binary string, then $R$ is obtained by repeating a shorter binary string $S$ for $K$ times. For example, if $S=101$ and $K=2$, then the binary representation of $R$ is $101101$. Since the result can be very large, you only need to output the total number of ways modulo $10^9+7$.

Input Format

The first line contains two positive integers $N$ and $K$.

The next line contains a string $S$ consisting of characters $0$ and $1$.

It is guaranteed that the first character of $S$ is $1$.

Output Format

Output one integer in one line, the number of valid selections modulo $10^9+7$.

3 1
100

1

Hint

Sample Explanation

The only valid selection is $\{1,2,3\}$.

Constraints

For $100\%$ of the testdata, $3 \le N \le 7$, $1 \le k \le 10^5$, $1 \le |S| \le 50$.

Translated by ChatGPT 5