JYY has recently been studying bitwise operations. He found that the most interesting bitwise operation is the XOR operation. For the XOR of two numbers, JYY discovered a conclusion: the XOR value of two numbers is 0 if and only if they are equal. JYY then began to wonder, what properties does the XOR value of $N$ numbers have?

JYY wants to know how many ways there are to choose $N$ distinct integers in the range $[0, R-1]$ such that the XOR sum of these $N$ integers is 0. (Different orders of selection are not counted as distinct; please refer to the examples.)

JYY is a computer scientist, so the $R$ in his mind is extremely large. For convenience, if we write $R$ as a 0-1 string, $R$ is obtained by repeating a shorter 0-1 string $S$, $K$ times. For example, if $S = \text{"101"}$ and $K = 2$, then the binary representation of $R$ is $\text{"101101"}$.

Since the result of the calculation can be very large, JYY only needs you to tell him the total number of ways modulo $10^9+7$.

Input

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

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

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

Output

Output a single integer representing the number of ways to choose the integers, modulo $10^9+7$.

Examples

Input 1

3 1
100

Output 1

1

Note

For the first example, the only way to choose the integers is $\{1, 2, 3\}$.

Input 2

5 100
1

Output 2

598192244

Constraints