E. 填数字

题目描述

给定字符串 $S$，$S$ 中的每个字符都是数字（$0, \dots, 9$）或 ?。 在通过用数字替换每次出现的 ? 而获得的整数中，当除以 $13$ 时有多少个余数为 $5$？ 整数可以以 $0$ 开头。 由于答案可能非常巨大，因此输出是要模 $10^9 + 7$。

输入格式

一行字符串 $S$

输出格式

一行一个整数

样例

输入样例 #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

数据范围与提示

• $1 \le |S| \le 10^5$
• 保证 $S$ 中只有数字或 ?