問題一覧 > 通常問題

No.1085 桁和の桁和

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 112
作問者 : tyawanmusityawanmusi / テスター : QCFiumQCFium
7 ProblemId : 3693 / 出題時の順位表
問題文最終更新日: 2020-06-20 01:23:50

お知らせ(6/20 1:23)

コーナーケースを追加し、リジャッジを行いました。

問題文

茶碗蒸しくんはある整数$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$の総数を$10^9+7$で割った余りを求めてください。
また、$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もしくは右上の雲マークをクリックしてアカウントを作成してください。