0, 1, 2 - Construction

2 secs 1024 MB
bayashiko's icon bayashiko

問題文

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

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

  

制約

  • 1N10001\leq N \leq 1000
  • 1M81\leq M \leq 8
  • 1K201\leq K \leq 20   

入力

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

N M KN \ M \ K

  

出力

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

  

入力例1

3 3 6

出力例1

25

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

入力例2

1 1 2

出力例2

1

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

入力例3

1000 8 10

出力例3

332011557

提出


Go (1.21)