问题描述

对于一个字符串 $A$，如果 $A$ 是由重复出现的子串 $"25"$ 构成的，例如 $A="25"$ 或者 $A="2525"$ 或者 $A="252525"$ ... 这样的形式，我们称其为“NicoNico字符串”。例如 $"25"$ 和 $"25252525"$ 是NicoNico字符串，但是 $"123"$ 和 $"225"$ 不是。

NiwanGo在一个网站上使用的密码是由长度为 $N$ 的数字串构成的。然而，NiwanGo忘记了密码的一部分。他记得从密码字符串中提取出满足条件的连续子串，使其构成一个NicoNico字符串的方式至少有 $X$ 种以上。但是需要注意的是，即使两个字符串相同，如果提取的位置不同，我们也将它们视为不同的子串。

请计算考虑的密码字符串可能的个数取模 $1,000,000,007 (10^9+7)$ 后的余数。

输入

输入以以下格式从标准输入中给出。

$N$ $X$ $S$

• 第1行是两个整数 $N (1 ≤ N ≤ 252)$ 和 $X (0 ≤ X ≤ 252)$，用空格隔开。表示密码的长度为 $N$ 并且至少有 $X$ 种以上的连续子串构成一个NicoNico字符串。
• 第2行是一个字符串 $S$，表示密码的信息。$S$ 是一个长度为 $N$ 的字符串，由数字 0 到 9 和 ? 构成。如果 $S$ 的第 $i$ 个字符
  • 是一个数字，表示密码的第 $i$ 个字符是该数字。
  • 是 ?，表示密码的第 $i$ 个字符的数字是未知的。

输出

输出考虑的密码字符串可能的个数取模 $1,000,000,007 (10^9+7)$ 后的余数，输出一行并以换行符结尾。

示例1

输入
3 1
2?5

输出
2

考虑的密码字符串有 $"225"$ 和 $"255"$ 这两个。

示例2

输入
15 4
???5????????9??

输出
976934094

注意密码的第1个字符可能是 0。

示例3

输入
4 10
1234

输出
0

很有可能出现没有遗忘任何部分的情况。

另外，也有可能不存在满足要求的子串，此时输出应为 $0$。