← 返回题目列表

AtCoder · dwango2015_finals_1

A. Niconico字符串2

中文机器翻译题面 查看原题

問題文

对于某个字符串 A 来说,A="25" 或 给出 A="2525" 或 给出 A="252525" ……以这种方式 "25" 重复若干次组成的字符串时,A 被称为尼科科字符串。例如 "25" 呀 "25252525" 是尼科科字符串,"123" 呀 "225" 不是尼科科字符串。

niwango君在某个网站上使用的密码sawawad,是由0 假设一直下雨,直到 9 的数字组成的长度 N 的字符串。但是,nikango 君忘记了密码的一部分。他记得从密码字符串中取出连续的子字符串,使其成为 nico 字符串的方法有 X 种以上。不过,即使字符串内容相同,只要取出的位置不同,也算作不同的情况。

请计算可作为密码的字符串数量除以 1,000,000,007 (10^9+7) 的余数。


入力

输入是按以下格式从标准输入给出的。

N X
S
  • 1 行中,2 整数 N (1 ≦ N ≦ 252), X (0 ≦ X ≦ 252) 以空格分隔给出。这是密码的长度 N ,表示取出能够成为 NIKONI C 字符串的连续子字符串的方法有 X 种以上。
  • 2 行表示密码的信息 1 个字符串 S 。 来自行S 是 可以通过兑换0 假设一直下雨,直到 9 的数字和 ? 组成的长度 N 的字符串中, 如果S 的 i 个字符是
    • 的数字,则表示密码的 i 个字符是该数字。 如果是
    • ? ,则表示密码的 i 个字符的数字未知。 请输出到

出力

请计算可作为密码的字符串数量除以 1,000,000,007 (10^9+7) 取模之后的余数 1 行。输出时在出口加入换行符。


入力例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 也可能没有任何位置。

另外,提取成为 nikoni 字符串的连续子字符串的方法 X 以上这样的字符串有时也不存在,但在这种情况下存在满足条件的字符串 0 个,因此, 只需输出0 。