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

[problemUrl]: https://atcoder.jp/contests/arc036/tasks/arc036_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 $ のどちらでも良いことを表す。

考えられる乱数表の総数を $ 1,000,000,007(=\ 1000000007) $ で割った余りを $ 1 $ 行に出力せよ。出力の末尾には改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ 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 条件を満たす乱数表は存在しません。