AT_dwango2015_finals_1 ニコニコ文字列２

对于某个字符串 $A$，如果 $A="25"$，或者 $A="2525"$，或者 $A="252525"$ ……，也就是说，$A$ 是由若干次重复 "25" 拼接而成的字符串，那么称 $A$ 为“ニコニコ字符串”。例如，"25" 和 "25252525" 是ニコニコ字符串，而 "123" 和 "225" 不是ニコニコ字符串。 ニワンゴ君在某个网站上使用的密码是由 `0` 到 `9` 的数字组成的长度为 $N$ 的字符串。然而，ニワンゴ君忘记了密码的部分内容。他记得，从密码字符串中可以取出的、是ニコニコ字符串的连续子串的方法有至少 $X$ 种。这里，即使字符串内容相同，只要取出的区间不同，也要分别计数。 请你求出，作为密码可能的字符串的个数，模 $1,000,000,007\ (10^9+7)$ 的结果。

输入通过标准输入给出，格式如下： > $N$ $X$ $S$ - 第 $1$ 行包含两个整数 $N\ (1 \leq N \leq 252),\ X\ (0 \leq X \leq 252)$，分别表示密码的长度为 $N$，以及可以取出的ニコニコ字符串的连续子串的方法数至少为 $X$。 - 第 $2$ 行包含一个字符串 $S$，表示密码的信息。$S$ 是一个长度为 $N$ 的字符串，仅由 `0` 到 `9` 的数字和 `?` 组成。$S$ 的第 $i$ 个字符含义如下： - 如果是数字，表示密码的第 $i$ 位就是该数字。 - 如果是 `?`，表示密码的第 $i$ 位可以是任意数字。

输出作为密码可能的字符串的个数，模 $1,000,000,007\ (10^9+7)$ 的结果。输出末尾需换行。

### 样例解释 1 作为密码可能的字符串有 "225" 和 "255" 共 $2$ 个。 ### 样例解释 2 注意，密码的第 $1$ 位也可以是 `0`。 ### 样例解释 3 像这样，忘记的部分可能一个都没有。此外，也可能不存在满足至少有 $X$ 个ニコニコ字符串子串的方法的字符串，这种情况下输出 $0$ 即可。 由 ChatGPT 4.1 翻译