数字游行

题目描述

给定字符串 $S$。$S$ 的每个字符是数字(0 到 9)或 ?。

把 ? 替换成数字后得到的整数中,除以 $13$ 余 $5$ 的数有多少个?这里,首位为 0 的情况也视为整数。

答案可能非常大,请输出答案除以 $10^9+7$ 的余数。

输入格式

输入按以下格式从标准输入给出:

$S$

输出格式

输出满足条件的整数个数除以 $10^9+7$ 的余数。

样例

??2??5

768

例如 $482305, 002865, 972665$ 等满足条件。

?44

1

只有 $044$ 满足条件。

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 \le |S| \le 10^5$