Digits Parade

题目描述

给定一个字符串 $S$。$S$ 中的每个字符要么是数字（$0$，...，$9$），要么是 $?$。 在通过将每个出现的 $?$ 替换为一个数字得到的整数中，有多少个在被 $13$ 除后余数为 $5$？一个整数可以以 $0$ 开头。 由于答案可能非常大，请输出答案对 $10^9+7$ 取模后的值。

输入格式

输入从标准输入给出，格式如下： $S$

输出格式

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

??2??5

768

?44

1

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 \leq |S| \leq 10^5$例如，$482305, 002865,$ 和 $972665$ 满足该条件。
只有 $044$ 满足该条件。
我们可能无法构造满足该条件的整数。

标签: AtCoder|abc135D

来源

AtCoder|abc135D