AT_abc135_d [ABC135D] Digits Parade

题目描述

给定一个字符串 $S$，$S$ 的每个字符要么是数字（0 到 9），要么是 ?。

请问，将所有的 ? 替换为数字后，能够得到多少个整数，这些整数除以 $13$ 的余数为 $5$？注意，即使整数的首位是 $0$，也视为有效整数。

由于答案可能非常大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

输入为一行，包含一个字符串 $S$。

输出格式

输出满足条件的整数个数，对 $10^9+7$ 取模后的结果。

样例 1

输入

??2??5

输出

768

样例 2

输入

?44

输出

1

样例 3

输入

7?4

输出

0

样例 4

输入

?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$

样例解释 1

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

样例解释 2

只有 $044$ 满足条件。

样例解释 3

也有可能无法构造出满足条件的整数。

由 ChatGPT 4.1 翻译