← 返回题目列表

AtCoder · arc036_c

C. 机会发生器

中文机器翻译题面 查看原题

問題文

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

高桥君受老板指示创建一个随机数表。

随机数表为 仅由 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