Problem Description

Takahashi works for a game company.

He has been instructed by his boss to create a random number table.

The random number table is a sequence of length $ N $ consisting only of $ 0 $ and $ 1 $, and some of its elements are already determined.

Takahashi also received a request from his boss not to create a random number table with a biased distribution. Specifically, for any contiguous subsequence taken from the random number table, the difference between the number of $ 0 $s and the number of $ 1 $s must be at most $ K $.

Takahashi decided to count how many such random number tables satisfy these conditions.

Input Format

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

$ N $ $ K $ $ S $

• The first line contains two integers $N\ (1\ ≦\ N\ ≦\ 300)$ and $K\ (1\ ≦\ K\ ≦\ N)$ separated by a space. This indicates that the length of the random number table is $ N $ and the maximum allowed difference is $ K $.
• The second line contains a string $ S $ of length $ N $ representing information about the random number table. The string $ S $ consists only of 0, 1, and ?. The $i\ (1\ ≦\ i\ ≦\ N)$th character from the left represents the information about the $ i $th element of the random number table.
• If the $ i $th character is 0, the $ i $th element of the random number table must be $ 0 $.
• If the $ i $th character is 1, the $ i $th element of the random number table must be $ 1 $.
• If the $ i $th character is ?, the $ i $th element of the random number table can be either $ 0 $ or $ 1 $.

Output Format

Output the total number of possible random number tables modulo $1,000,000,007(=\ 1000000007)$ in one line. End the output with a newline.

Sample Input and Output

Sample Input #1

9 4
?011?1110

Sample Output #1

2

Sample Input #2

9 3
?011?1110

Sample Output #2

0

Sample Input #3

9 1
???1?????

Sample Output #3

1

Sample Input #4

12 5
???0??1??11?

Sample Output #4

172

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $N\ ≦\ 12$, you will be awarded $ 10 $ points.
• If you solve the dataset where $K\ ≦\ 5$, you will be awarded an additional $ 30 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 60 $ points.

Sample Explanation 1

Consider the random number table \\[$ 0 $, $ 0 $, $ 1 $, $ 1 $, $ 0 $, $ 1 $, $ 1 $, $ 1 $, $ 0 $\\\]. In this table, the maximum difference between the number of $ 0 $s and $ 1 $s is $4(=\ 5\ -\ 1)$ for the subsequence \\[$ 1 $, $ 1 $, $ 0 $, $ 1 $, $ 1 $, $ 1 $\\\] starting from the 3rd element to the 8th element. Another valid table is \\[$ 1 $, $ 0 $, $ 1 $, $ 1 $, $ 0 $, $ 1 $, $ 1 $, $ 1 $, $ 0 $\\\].

Sample Explanation 2

No random number table satisfies the conditions.

见题面 Input 部分

见题面 Output 部分