p02960 AtCoder Beginner Contest 135 - Digits Parade
Given is a string S. Each character in S is either a digit (`0`, ..., `9`) or `?`.

Among the integers obtained by replacing each occurrence of `?` with a digit, how many have a remainder of 5 when divided by 13? An integer may begin with 0.

Since the answer can be enormous, print the count modulo 10^9+7.

Constraints

* S is a string consisting of digits (`0`, ..., `9`) and `?`.
* 1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:


S


Output

Print the number of integers satisfying the condition, modulo 10^9+7.

Examples

Input

??2??5


Output

768


Input

?44


Output

1


Input

7?4


Output

0


Input

?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???


Output

153716888
```python
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(10) if c == '?' else (int(c),)
    a = [sum(a[(i - p * j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])
```