D - 数字巡游

得分：$400$ 分

问题描述

给定一个字符串 $S$。$S$ 中的每个字符都是数字 (0, ..., 9) 或者 ?。

在将每个 ? 替换为一个数字之后得到的整数中，有多少个除以 $13$ 的余数为 $5$？一个整数可能以 $0$ 开始。

由于答案可能很大，将计数结果对 $10^9+7$ 取模后输出。

约束条件

• $S$ 是由数字 (0, ..., 9) 和 ? 构成的字符串。
• $1 \leq |S| \leq 10^5$

输入

从标准输入中按以下格式输入：

$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