AT_arc156_e [ARC156E] Non-Adjacent Matching

[problemUrl]: https://atcoder.jp/contests/arc156/tasks/arc156_e 長さが $ N $、各要素が $ 0 $ 以上 $ M $ 以下、総和が $ K $ 以下の整数列のうち、**良い数列** の個数を $ 998244353 $ で割ったあまりを求めてください。 ここで、長さ $ N $ の数列 $ X=(X_1,X_2,\ldots,X_N) $ は以下の条件を全て満たすグラフ $ G $ が存在するとき、かつ、そのときに限り良い数列です。 - $ G $ は $ 1 $ から $ N $ の番号がついた $ N $ 頂点からなる、自己ループを持たないグラフである。（多重辺はあってもよい。） - 各 $ i\ (1\leq\ i\ \leq\ N) $ について、頂点 $ i $ の次数は $ X_i $ である。 - 各 $ i\ (1\leq\ i\ \leq\ N) $ について、頂点 $ i $ と頂点 $ i+1 $ を結ぶ辺は存在しない。ここで、頂点 $ N+1 $ は頂点 $ 1 $ を意味する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $

答えを出力せよ。

### 制約 - $ 4\ \leq\ N\ \leq\ 3000 $ - $ 0\ \leq\ M\ \leq\ 3000 $ - $ 0\leq\ K\ \leq\ NM $ - 入力される数値は全て整数 ### Sample Explanation 1 条件を満たす良い数列は以下の $ 3 $ 個です。 - $ (0,0,0,0) $ - $ (0,1,0,1) $ - $ (1,0,1,0) $ ### Sample Explanation 3 $ 998244353 $ で割ったあまりを答えてください。