#ABC135D. Digits Parade
Digits Parade
题目描述
Given is a string . Each character in is either a digit (0
, ..., 9
) or ?
.
Among the integers obtained by replacing each occurrence of ?
with a digit, how many have a remainder of when divided by ? An integer may begin with .
Since the answer can be enormous, print the count mod .
给定的是一个字符串 。 中的每个字符要么是数字(
0
, ...,9
),要么是`?在用一个数字替换
?
后得到的整数中,除以 后余数为 的有多少个?一个整数可以以 开头。由于答案可能很庞大,请打印模数 。
输入格式
输入内容按以下格式标准输入:
输出格式
打印满足条件的整数个数,取模 。
样例 #1
样例输入 #1
??2??5
样例输出 #1
768
样例 #2
样例输入 #2
?44
样例输出 #2
1
样例 #3
样例输入 #3
7?4
样例输出 #3
0
样例 #4
样例输入 #4
?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???
样例输出 #4
153716888
说明
数据规模与约定
- 是一个由数字(
0
, ...,9
)和?
组成的字符串。
样例 解释
例如, 和 满足条件。
样例 解释
只有 满足条件。
样例 解释
我们可能无法生成满足条件的整数。