AT_arc036_c [ARC036C] 偶然ジェネレータ

### 题目简介 有一个长度为$N$的数列，其仅由$0,1$构成。 现在，有一些地方需要填充，这些地方用问号来代替。 需要知道，有几种方案来填充问号，使得无论从数列中取出怎样的**连续的**子数列，其子数列中所包含的$0$的个数和$1$的个数的差都必须在$K$以下。

- 在第$1$行中，有两个正整数$N(1 \le N \le 300)$和$K(1 \le K \le N)$。这表示数列的长度为$N$，子数列允许的最大差为$K$。 - 第$2$行提供长度为$N$的字符串，表示这个数列。字符串仅由$0$、$1$和问号构成 - 如果从左起$i$个字符是$0$，则表示随机数表的第$i$个元素必须是$0$。 - 如果从左起$i$个字符是$1$，则表示随机数表的第$i$个元素必须是$1$。 - 如果从左起第$i$个字符是问号，则随机数表的第$i$个元素是$0$和$1$都可以（也就是需要填充）。

输出填充数列中问号的方案的总数对$10^9+7$取模，**末尾要换行。**

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 12 $ を満たすデータセットに正解した場合は、$ 10 $ 点が与えられる。 - $ K\ ≦\ 5 $ を満たすデータセットに正解した場合は、上記とは別に $ 30 $ 点が与えられる。 - 追加制約のないデータセットに正解した場合は、上記とは別に $ 60 $ 点が与えられる。 ### Sample Explanation 1 乱数表として \\\[$ 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 $\\\] が条件を満たします。 ### Sample Explanation 2 条件を満たす乱数表は存在しません。