問題文

ある文字列 A について、A="25" または A="2525" または A="252525" ... というふうに "25" を何回か繰り返した文字列になっているとき、A はニコニコ文字列であるといいます。たとえば "25" や "25252525" はニコニコ文字列ですが、"123" や "225" はニコニコ文字列ではありません。

ニワンゴ君があるサイトで使っているパスワードは、0 から 9 の数字から成る長さ N の文字列です。しかし、ニワンゴ君はパスワードの一部を忘れてしまいました。ニコニコ文字列となるような連続した部分文字列をパスワードの文字列から取り出す方法が X 通り以上あることは覚えています。ただし、文字列として同じであっても、取り出し位置が異なっていれば別々に数えたものとします。

パスワードとして考えられる文字列の個数を 1,000,000,007 (10^9+7) で割った余りを求めてください。

入力例1

3 1
2?5

出力例1

2

パスワードとして考えられる文字列は "225" と "255" の 2 つです。

入力例2

15 4
???5????????9??

出力例2

976934094

パスワードの 1 文字目は 0 でも良いことに注意してください。

入力例3

4 10
1234

出力例3

0

このように、忘れている部分が 1 箇所もないこともありえます。

また、ニコニコ文字列となるような連続した部分文字列を取り出す方法が X 以上であるような文字列が存在しないこともありますが、この場合は条件を満たす文字列が 0 個なので、0 を出力すれば良いです。