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$.