J20 例题-4 解锁宝箱

题目描述

历尽千辛万苦，勇者小喵终于战胜了千年恶龙。恶龙掉落了一个史诗级的宝箱，需要解决一个字谜游戏才能打开。

这个字谜游戏由一个仅由数字 $0\sim 9$ 或 ? 组成的字符串 $S$ ， 小喵需要将这些 ? 替换为 数字，使其满足以下条件：

• 该数字除以 $13$ 的余数为 $5$ ；

所有满足条件的方案数模 $10^9+7$ 就是打开宝箱的密码，小喵需要计算出这个密码是多少。

输入格式

一行一个仅由数字 $0\sim 9$ 或 ? 组成的字符串 $S$ 。

输出格式

一行一个整数，输出宝箱的密码。

样例输入1

??2??5

样例输出1

768

样例1解析

$482305, 002865,972665$ 是其中三个满足条件的方案。

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

数据范围

$100 \%$ 的数据：$1\leq |S| \leq 10^5$。