入力

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

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 行に出力せよ。出力の末尾には改行を入れること。