题目描述

文字列 $S$ が与えられます。$S$ の各文字は、数字 (0 ～ 9) か ? です。

? を数字に置き換えてできる整数のうち、$13$ で割って $5$ あまる数は何通りあるでしょうか？ただし、頭文字が $0$ である場合も整数とみなすものとします。

答えは非常に大きくなる可能性があるため、$10^9+7$ で割ったあまりを答えてください。

输入格式

入力は以下の形式で標準入力から与えられます。

$S$

输出格式

条件を満たす整数の個数を $10^9+7$ で割ったあまりを出力してください。

题目大意

给定的是字符串 S。S 中的每个字符都是数字（0，...，9）或 ？。

在通过用数字替换每次出现的 ？ 而获得的整数中，当除以 $13$ 时有多少个余数为 $5$？整数可以以 $0$ 开头。

由于答案可能非常巨大，因此输出是要模 $10^{9} + 7$

??2??5

768

?44

1

7?4

0

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

153716888

提示

制約

• $S$ は数字 (0 ～ 9) と ? からなる文字列。
• $1\ \leq\ |S|\ \leq\ 10^5$

Sample Explanation 1

たとえば $482305,\ 002865,\ 972665$ などが条件を満たします。

Sample Explanation 2

$044$ のみが条件を満たします。

Sample Explanation 3

条件を満たす整数を作ることが不可能な場合もあります。