Navi has adopted a bunny. Recently, he wants to train his bunny to do a trick for his friends.

Navi prepared a horizontal strip divided into n cells, where the i-th cell from the left is denoted by cell i. Each cell has either a number \(a_{i}\) is written in it or is blank. He places the bunny in cell 1 and wants it to reach cell n, while visiting all the cells exactly once. However, the range that a bunny can jump is limited. Navi's bunny can jump at most d units in one jump. Thus, from cell i, the bunny can only reach all cells between \(i - d\) and \(i + d\) inclusive.

Moreover, there is a special rule. If the bunny is standing on a cell i with a digit x written on it, then it has to jump exactly x units in the next move, i.e. it can only jump to cell \(i - x\) or \(i + x\) in the next move.

Navi wonders how many ways are there for the bunny to jump from cell 1 to n while visiting each cell exactly once. Help Navi find the number of ways this can be done, modulo \(10^{9} + 7\).

Input Format:
The first line of input contains a string a, where \(a_{i}\) denotes the value written in cell i. If cell i is blank, then \(a_{i}\) is equal to '?' (without quotes) instead. It is guaranteed that if \(a_{i}\) is not a question mark, then \(a_{i}\) is a digit from 1 to d inclusive.

The next line of input contains a single integer d, denoting the maximum distance the bunny can jump in one move.

Output Format:
Output a single integer, the number of ways the bunny can perform the jumps, modulo \(10^{9} + 7\).

Constraints:
\(1 \leqslant |a| \leqslant 500\).
\(1 \leqslant d \leqslant 5\).