AT_abc135_d.[ABC135D] Digits Parade
普及/提高-
通过率：0%
AC君温馨提醒
该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。
题目描述
给定一个字符串 S，S 的每个字符要么是数字（0 到 9），要么是 ?。
请问，将所有的 ? 替换为数字后，能够得到多少个整数，这些整数除以 13 的余数为 5？注意，即使整数的首位是 0，也视为有效整数。
由于答案可能非常大，请输出答案对 109+7 取模后的结果。
输入格式
输入为一行，包含一个字符串 S。
输出格式
输出满足条件的整数个数，对 109+7 取模后的结果。
输入输出样例
输入#1
??2??5
输出#1
768
输入#2
?44
输出#2
1
输入#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
说明/提示
限制条件
- S 由数字（
0到9）和?组成。 - 1≤∣S∣≤105
样例解释 1
例如 482305、002865、972665 等都满足条件。
样例解释 2
只有 044 满足条件。
样例解释 3
也有可能无法构造出满足条件的整数。