Little Mislav is still visiting water lilies on a quiet branch of the Sava river near his town. Along the branch, there are $n$ water lilies numbered from 1 to $n$ from left to right. Some of the water lilies are blocked, while others are free, and Mislav can jump on them. In one jump, Mislav can jump at most $k$ water lilies away — if he is currently on water lily $a$, he can jump to a free water lily $b$ if $|a - b| \le k$.
Figure 1: One cycle from the first example test case.
Mislav wants to find a cycle in which he jumps to every free water lily exactly once and which ends on the same water lily where the jumping started. Two cycles are equal if the order of the water lilies visited is the same, regardless of the fact that the cycles might not start with the same water lily. Thus, in the example in the figure, the cycles 2–3–6–4–2 and 6–4–2–3–6 are considered equal, while the cycles 2–3–6–4–2 and 2–4–6–3–2 are considered different.
For a given sequence of water lilies and the maximum jump length $k$, determine the number of different cycles modulo $10^9 + 7$.
Input
The first line contains the natural numbers $n$ and $k$ — the number of water lilies and the maximum jump length. The next line contains a sequence of $n$ characters — the $j$-th character in the sequence is "0" if water lily $j$ is free, and "1" if it is blocked. At least three water lilies will be free.
Output
Print a single number — the required number of cycles modulo $10^9 + 7$.
Subtasks
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 10 | $n \le 20, 3 \le k \le 5$ |
| 2 | 40 | $n \le 100, k = 3$ |
| 3 | 50 | $n \le 100, 3 \le k \le 5$ |
Examples
Input 1
6 3 100010
Output 1
2
Input 2
8 4 10000001
Output 2
72
Input 3
10 5 0010000100
Output 3
428