F - Find 810s

配点 : $400$ 点
　　

問題文

長さが $N$ であり、全ての要素が $0$ 以上 $M$ 以下であるような整数列のうち、以下の条件を満たすものの個数を $998244353$ で割った余りを求めてください。

• 整数列全体を繋げて $1$ つの文字列として見たとき、その連続とは限らない部分列として、 810 を $K$ 回繋げたものが存在する。

整数列全体を繋げて $1$ つの文字列として見るとは、整数列の各要素を文字列として見て、順番を並び替えずに結合し $1$ つの文字列として扱うことを意味します。例えば、 $(10,20,0,31)$ なら 1020031 として扱います。

$(8,1)$ を $(8,01)$ として 801 として扱うなど、余計なleading-zeroを付けることは許されません(そのため、ある整数列がどのような文字列として扱われるかは一意に定まります)。

また、 $1$ つの文字列として見た結果が同じでも、整数列として異なるならば区別します。

制約

• $1 \leq N,M,K \leq 1000$
• 入力は全て整数 　　

入力

入力は以下の形式で標準入力から与えられます。

出力

答えを出力してください。

入力例1

2 81 1

出力例1

18

条件を満たす整数列は以下の $18$ 個です。

• $(8,10),(18,10),(28,10),(38,10),(48,10),(58,10),(68,10),(78,10),(80,10),$
  $(81,0),(81,10),(81,20),(81,30),(81,40),(81,50),(81,60),(81,70),(81,80)$ 　

入力例2

6 9 2

出力例2

1

長さが $6$ 、各要素が $0$ 以上 $9$ 以下の整数列のうち、 810 を $2$ 回繋げたものである 810810 を部分列として含むのは $(8,1,0,8,1,0)$ の $1$ つのみです。

入力例3

1000 1000 334

出力例3

755221108

答えを $998244353$ で割った余りを求めることに注意してください。