分数: 400 点
问题陈述
给定的是一个字符串 S。中的每个角色 S 是一个数字 (0, ..., 9)或 ?.
在通过替换每次出现的整数而获得的 ? 与一个数字,有多少个余数 5 除以 13?整数可以开头为 0.
由于答案可能很大,因此打印计数模数 10^9+7.
约束
- S 是由数字 (
0, ...,9)和?. - 1 \leq |S| \leq 10^5
输入
输入由标准输入按以下格式给出:
S
输出
打印满足条件的整数个数,取模 10^9+7.
示例输入 1
??2??5
示例输出 1
768
例如, 482305, 002865, 和 972665 满足条件。 仅
示例输入 2
?44
示例输出 2
1
仅有的 044 满足条件。
示例输入 3
7?4
示例输出 3
0
我们可能无法产生满足条件的整数。
示例输入 4
?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???
示例输出 4
153716888