Mislav 正在拜访他家乡附近萨瓦河（Sava）一条平静支流上的睡莲。沿支流从左到右生长着 $n$ 朵睡莲，编号为 $1$ 到 $n$。其中一些睡莲被阻碍了，而其余的则是未被阻碍的，Mislav 可以在它们之间跳跃。Mislav 一次最多可以跳跃 $k$ 的距离 —— 如果他当前位于睡莲 $a$，那么当 $|a - b| \le k$ 时，他可以跳到未被阻碍的睡莲 $b$ 上。
图 1：第一个样例数据中的一个环。
Mislav 想要找到一个环，该环恰好访问每个未被阻碍的睡莲一次，并最终回到开始跳跃的起点睡莲。如果两个环访问睡莲的顺序相同（不考虑起点），则认为它们是相同的。因此，在图中的例子中，环 2–3–6–4–2 和 6–4–2–3–6 被认为是相同的，而环 2–3–6–4–2 和 2–4–6–3–2 被认为是不同的。
给定睡莲的排列和最大跳跃长度 $k$，求不同环的数量模 $10^9 + 7$ 的余数。
输入格式
第一行包含正整数 $n$ 和 $k$ —— 睡莲的数量和最大跳跃长度。
下一行包含一个由 $n$ 个字符组成的字符串 —— 如果第 $j$ 个睡莲未被阻碍，则字符串中的第 $j$ 个字符为 0；如果被阻碍，则为 1。
保证至少有三个睡莲未被阻碍。
输出格式
输出一个整数 —— 所求的环的数量模 $10^9 + 7$ 的余数。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 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$ |
样例
输入样例 1
6 3 100010
输出样例 1
2
输入样例 2
8 4 10000001
输出样例 2
72
输入样例 3
10 5 0010000100
输出样例 3
428