お知らせ

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$の桁和で置き換える

制約

• $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$で割った余りを出力してください。
最後に改行してください。

サンプル

13?3
1

1

123456789
0

0

012?
3

2

1?2?3?4?5?6?7?8?9?0?
9

111111105