No.1085 Digit Sum of Digit Sum
タグ : / 解いたユーザー数 147
作問者 :
tyawanmusi
/ テスター :
QCFium
Announcements
6/20 1:23 A corner case was added and a rejudge was performed.
8/12 17:28 There was a case that violated the constraints (now fixed).
Problem Statement
Chawanmushi-kun received a sheet of paper with an integer $S$ written on it from the God of Paper.
However, part of the paper cannot be seen because of the god's radiance.
You are given a string $T$ representing how $S$ appears.
The length of $T$ is equal to the length of $S$, and each character of $T$ is one of 0~9,?.
For the $i$-th character of $T$ $(1 \le i \le |S|)$: if it is ?, the $i$-th character of $S$ cannot be seen; otherwise, the $i$-th character of $S$ is the same as the $i$-th character of $T$.
The god gave Chawanmushi-kun the following hint.
After performing the following operation $20200619^{20200619}$ times, $S$ is equal to $D$.
- Replace $S$ with the digit sum of $S$
Note that the 1st character of $S$ may be $0$.
Constraints
- $1 \le |T| \le 10^5$
- $0 \le D \le 9$
- Each character of $T$ is one of
0~9,? - $D$ is an integer
Input
$T$
$D$
$T$ is given on the $1$st line.
$D$ is given on the $2$nd line.
Output
Output the total number of possible $S$, modulo $10^9+7$.
Print a newline at the end.
Sample
Sample 1
Input
13?3
1
Output
1
When $S = 1333$, $S$ changes as $1333 → 10 → 1 → 1 →\dots$, and becomes equal to $D$.
This is the only case in which $S$ after the operations is equal to $D$.
Sample 2
Input
123456789
0
Output
0
The integer may be entirely visible.
Also, the answer may be $0$.
Sample 3
Input
012?
3
Output
2
The 1st character of $T$ may be 0 or ?.
Sample 4
Input
1?2?3?4?5?6?7?8?9?0?
9
Output
111111105
Output the answer modulo $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。