問題文
高桥君在一家游戏公司工作。
高桥君受老板指示创建一个随机数表。
随机数表为 仅由 0,1 之一组成的长度 N 是一个数字序列,确定哪些值存储在某些元素中。
顺便说一句,高桥君还收到了老板的命令,“我不希望你创建一个分布过于偏向的随机数表。”具体来说,无论从随机数表中提取出什么样的连续子序列, 0 的数量和 1 的数量差异为 必须小于或等于 K 。
高桥君决定统计满足这些条件的随机数表的总数。
入力
输入是按以下格式从标准输入给出的。
N K S
- 1 行中,2 整数 N (1 ≦ N ≦ 300) 和 在 K (1 ≦ K ≦ N) 用空格分隔。这意味着随机数表的长度为 N 其中最大允许差异是 K 。
- 2 行包含表示有关随机数表的信息的长度。 N 字符串
给出了 S 。字符串
它仅由 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 行输出。在输出末尾添加换行符。
入力例1
9 4 ?011?1110
出力例1
2
作为随机数表[ 考虑0, 0, 1, 1, 0, 1, 1, 1, 0]。在这个随机数表中,0 的数量和 1 数量的最大可能差异是从左边开始 3 第一个元素, 从末尾第8 个元素开始的长度 序列 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