0, 1, 2 - Construction

問題文

長さが $N$ であり、全ての要素が $0,1,2$ のいずれかであるような数列は全部で $3^N$ 個ありますが、そのうち以下の条件を満たすものの個数を $998244353$ で割った余りを求めてください。

• 長さ $M$ の連続部分列であって、その総和が $K$ の倍数であるようなものが存在しない。

制約

• $1\leq N \leq 1000$
• $1\leq M \leq 8$
• $1\leq K \leq 20$ 　　

入力

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

出力

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

入力例1

3 3 6

出力例1

25

$(0,0,0),(2,2,2)$ 以外の計 $25$ 個の数列が条件を満たします。 　
　

入力例2

1 1 2

出力例2

1

$(1)$ のみが条件を満たします。　
　

入力例3

1000 8 10

出力例3

332011557