Problem E
Erased Numbers

equation on a blackboard with numbers erased

Alice walks into binary math class late one day but it was too late. Somebody had erased all the numbers on the blackboard! All that is left now are the addition and multiplication operators and the final number the mystery equation is equal to. The class is binary math class so all numbers are some power of two. She knows that there can be multiple possible equations so with no better option, she will guess one of the possible ways to fill in the equation. Help her calculate how many possible answers there are so that she can at least impress her teacher so that he might possibly not deduct all of her points. Since the number might get very large, compute the remainder of that number when divided by $10^9+7$.

The equation left on the blackboard may look like the one below where ? could be any nonnegative power of two.

? * ? + ? = 3

In the example above, there are $3$ possible ways to fill in the ?, namely,

2 * 1 + 1 = 3
1 * 2 + 1 = 3
1 * 1 + 2 = 3

Note:

• All ? are integers of the form $2^{p}$ where $p$ is an integer with $p \ge 0$.

• $10^9 + 7$ is a prime number.

Input

The first line contains two integers, $n$ and $k$ ($1 \le n \le 100, 1 \le k \le 10^5$), where $n$ is the number of ? in the equation given in the next line and $k$ is the number the left-hand side of the equation is equal to. The second line is a string $s$ of length $2n-1$ composed of $n$ question marks (?) and $n-1$ arithmetic operators, each of which is * or +.

Output

Output a single nonnegative integer $p \pmod{10^9 + 7}$ where $p$ is the number of different ways to fill in the question marks in the equation and get number $k$.

3 3
?*?+?

3

5 10
?+?*?+?*?

30

5 5
?+?*?+?*?

8

1 1
?

1