Problem Statement

高橋くんはゲーム会社に勤めている。

高橋くんは上司から、乱数表を作るよう指示を受けた。

乱数表は $0,1$ のいずれかでのみ構成される長さ $N$ の数列で、そのうちいくつかの要素には、どちらの値が入るかが決まっている。

ところで高橋くんは、上司から「あまり分布が偏った乱数表は作らないでほしい」という注文も受けている。具体的には、乱数表からどのような連続する部分列を取り出しても、その部分列に含まれる $0$ の個数と $1$ の個数の差が $K$ 以下でなければならない。

高橋くんはこのような条件を満たす乱数表が全部でいくつあるのか数えることにした。

Input

入力は以下の形式で標準入力から与えられる。

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$ 番目の要素についての情報を表す。

部分点

この問題には部分点が設定されている。

• $N ≦ 12$ を満たすデータセットに正解した場合は、$10$ 点が与えられる。
• $K ≦ 5$ を満たすデータセットに正解した場合は、上記とは別に $30$ 点が与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に $60$ 点が与えられる。

Output

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