No.1085 桁和の桁和
タグ : / 解いたユーザー数 142
作問者 :
tyawanmusi
/ テスター :
QCFium
お知らせ
6/20 1:23 コーナーケースを追加し、リジャッジを行いました。
8/12 17:28 制約違反のケースがありました(修正済み)
問題文
茶碗蒸しくんはある整数$S$が書かれた紙を紙の神様から貰いました。
しかし、紙の一部が神様の威光のせいで見えません。
$S$の見え方を表す文字列$T$が与えられます。
$T$の長さと$S$の長さは等しく、$T$の各文字は0~9,?のいずれかです。
$T$の$i$文字目$(1 \le i \le |S|)$は、?なら$S$の$i$文字目が見えないことを表し、そうでなければ$S$の$i$文字目は$T$の$i$文字目と同じです。
神様は茶碗蒸しくんに次のヒントを教えてくれました。
次の操作を$20200619^{20200619}$回行った時、$S$と$D$は等しい。
- $S$を$S$の桁和で置き換える
また、$S$の1文字目が$0$であることがあります。
制約
- $1 \le |T| \le 10^5$
- $0 \le D \le 9$
- $T$のそれぞれの文字は
0~9,?のいずれかである - $D$は整数である
入力
$T$
$D$
$1$行目には$T$が入力されます。
$2$行目には$D$が入力されます。
出力
ありうる$S$の総数を$10^9+7$で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
13?3
1
出力
1
$S = 1333$のとき、$S$は$1333 → 10 → 1 → 1 →\dots$となり、$D$と等しくなります。
操作後の$S$が$D$と等しくなるのはこの1通りのみです。
サンプル2
入力
123456789
0
出力
0
整数が全て見えている場合もあります。
また、答えが$0$となる場合もあります。
サンプル3
入力
012?
3
出力
2
$T$の1文字目が0や?になることもあります。
サンプル4
入力
1?2?3?4?5?6?7?8?9?0?
9
出力
111111105
答えを$10^9+7$で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。