问题

高桥君在一家游戏公司工作。

高桥君收到上司的指示，要他制作一个随机数表。

随机数表是由 0 和 1 组成的长度为 N 的数列，其中一些元素的值已经确定。

顺便说一句，高桥君还接到了上司的订单，要求他不要制作偏向某一方的随机数表。具体来说，从随机数表中取出任何连续的子序列，该子序列中包含的 0 的个数和 1 的个数之差必须不超过 K。

高桥君决定计算满足这种条件的随机数表的总数。

---

输入

输入以以下格式从标准输入中给出。

N K S

• 第 1 行包含两个整数 N (1 <= N <= 300) 和 K (1 <= K <= N)，以空格分隔。表示随机数表的长度为 N，允许的最大差值为 K。

• 第 2 行包含一个描述随机数表的字符串 S，其长度为 N。字符串 S 仅由 '0'、'1' 和 '?' 构成，并且第 i (1 <= i <= N) 个字符表示随机数表中第 i 个元素的信息。

  • 如果第 i 个字符为 '0'，则表示随机数表的第 i 个元素必须为 0。
  • 如果第 i 个字符为 '1'，则表示随机数表的第 i 个元素必须为 1。
  • 如果第 i 个字符为 '?'，则表示随机数表的第 i 个元素可以是 0 或者 1。

部分得分

本题设有部分得分。

• 对于满足 N <= 12 的数据集，正确回答将获得 10 分。
• 对于满足 K <= 5 的数据集，除上述分数外，还将额外获得 30 分。
• 对于没有其他限制条件的数据集，除上述分数外，还将额外获得 60 分。

输出

输出计算得到的可能的随机数表的总数，然后再对 1,000,000,007 ( = 1000000007 ) 取模，最后换行。

---

示例输入1

9 4
?011?1110

示例输出1

2

作为随机数表，我们考虑 [$0$, $0$, $1$, $1$, $0$, $1$, $1$, $1$, $0$]。在这个随机数表中，可以找到一个长度为 6 的子序列 [$1$, $1$, $0$, $1$, $1$, $1$]，其差值为 4 (= 5 - 1)。

此外，还有一个满足要求的随机数表 [$1$, $0$, $1$, $1$, $0$, $1$, $1$, $1$, $0$]。

---

示例输入2

9 3
?011?1110

示例输出2

0

不存在满足条件的随机数表。

---

示例输入3

9 1
???1?????

示例输出3

1

---

示例输入4

12 5
???0??1??11?

示例输出4

172