Problem Description

For a given string $ A $, if $ A = "25" $ or $ A = "2525" $ or $ A = "252525" $ ..., i.e., $ A $ is a string that repeats "25" multiple times, then $ A $ is called a Niconico string. For example, "25" and "25252525" are Niconico strings, but "123" and "225" are not.

Niwango's password on a certain site is a string of length $ N $ consisting of digits from 0 to 9. However, Niwango has forgotten some parts of the password. He remembers that there are at least $ X $ ways to extract contiguous substrings from the password that are Niconico strings. Note that even if the substrings are the same, they are counted separately if they are extracted from different positions.

Find the number of possible passwords modulo $1,000,000,007\ (10^9+7)$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ X $ $ S $

• The first line contains two integers $N\ (1 \leq N \leq 252)$ and $X\ (0 \leq X \leq 252)$ separated by a space. This indicates that the password length is $ N $ and there are at least $ X $ ways to extract contiguous substrings that are Niconico strings.
• The second line contains a string $ S $ of length $ N $ consisting of digits from 0 to 9 and ?. The $ i $-th character of $ S $ represents:
• If it is a digit, the $ i $-th character of the password is that digit.
• If it is ?, the $ i $-th character of the password is unknown.

Output Format

Output the number of possible passwords modulo $1,000,000,007\ (10^9+7)$ in one line. End the output with a newline.

Sample Input and Output

Sample Input #1

3 1
2?5

Sample Output #1

2

Sample Input #2

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

Sample Output #2

976934094

Sample Input #3

4 10
1234

Sample Output #3

0

Notes/Hints

Sample Explanation 1

The possible passwords are "225" and "255", totaling 2.

Sample Explanation 2

Note that the first character of the password can be 0.

Sample Explanation 3

It is possible that there are no unknown parts. Also, there might be no strings that satisfy the condition of having at least $ X $ Niconico substrings. In this case, since there are 0 valid strings, output 0.

见题面 Input 部分

见题面 Output 部分