Kapil wants to organise a party. But due to covid restriction, he can invite only limited number of guests. To determine the total invitation, he has 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, total number of invitations will be equal to 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⁹ + 7.

Constraints

• S is a string consisting of digits (0, ..., 9) and ?.
• 1 ≤ |S| ≤ 10⁵

Input

Input is given from Standard Input in the following format: S

Output

Print the number of invitations satisfying the condition, modulo 10⁹ + 7.