← 返回题目列表

AtCoder · abc135_d

D. 数字游行

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

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

在通过替换每次出现的整数而获得的 ? 与一个数字,有多少个余数 5 除以 13?整数可以开头为 0.

由于答案可能很大,因此打印计数模数 10^9+7.

约束

  • S 是由数字 (0, ..., 9)和 ?.
  • 1 \leq |S| \leq 10^5

输入

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

S

输出

打印满足条件的整数个数,取模 10^9+7.


示例输入 1

??2??5

示例输出 1

768

例如, 482305, 002865, 和 972665 满足条件。 仅


示例输入 2

?44

示例输出 2

1

仅有的 044 满足条件。


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