問題
$N$桁の正整数$S$が与えられます。ただし、$S$の中にはいくつかの'$?$'が含まれる場合があります。
$S$の中の'$?$'をそれぞれ0以上9以下の数字に置き換える方法のうち、$S$が$K$で割り切れるものは何通りですか。
998244353で割った余りを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $K$ $S$
1行目に整数$N,K$が与えられる。 2行目に整数$S$が与えられる。
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N,K \leq 3000$
入出力例
入力例1
3 10 ?8?
出力例1
10
二つ目の'$?$'を0に置き換えれば、一つ目の'$?$'を何に置き換えても$S$は$K$で割り切れます。よって、一つ目の'$?$'は0~9の10通りで置き換えることが出来るので10を出力します。
$S$の先頭を0に置き換えても構いません。
入力例2
9 13 9?82??35?
出力例2
768