注意

この問題のTLは $8$ secです。

問題文

Not Negative

整数列 $X_1,X_2,\dots ,X_N$ が与えられます。

あなたは以下の操作を $0$ 回以上行うことができます。

ある要素 $X_i$ を選択する。その後、以下の $3$ 個の行動を同時に行う。

• もし $X_{i-1}$ が存在するならば $X_{i-1}=X_{i-1}+X_i$ とする。
• もし $X_{i+1}$ が存在するならば $X_{i+1}=X_{i+1}+X_i$ とする。
• $X_i=-X_i$ とする。

$X$ の全ての要素を非負にするために必要な操作の最小回数を求めてください。有限回の操作で $X$ の全ての要素を非負にできることが証明可能です。

しかし、PCT君は $X$ の要素を全て忘れてしまい、落ち込んでしまいました。しかし、$X$ の要素の絶対値は $K$ でないことは覚えていました。そこで問題を以下のように変更しました。

Don't be Negative!

全ての要素が $-M$ 以上 $M$ 以下かつ絶対値が $K$ でない整数である長さ $N$ の数列 $A_1,A_2,\dots ,A_N$ 全てに対して Not Negative を解き、解の総和を $mod998244353$ で求めてください。

ネガティブになっているPCT君を元気付けるために Don't be Negative! を解いてください。

入力

$NMK$

• 入力は全て整数である。
• $1\le N\le 4\times {10}^4$
• $1\le M\le 4$
• $0\le K\le M$

出力

Don't be Negative の解を出力してください。

サンプル

2 1 0

5

3 3 2

306

10 4 2

49870937

2021 4 0

180258189