AT_abc253_e [ABC253E] Distance Sequence

[problemUrl]: https://atcoder.jp/contests/abc253/tasks/abc253_e 長さ $ N $ の整数からなる数列 $ A=(A_1,\ldots,A_N) $ であって、以下の条件を全て満たすものは何通りありますか？ - $ 1\le\ A_i\ \le\ M $ $ (1\ \le\ i\ \le\ N) $ - $ |A_i\ -\ A_{i+1}|\ \geq\ K $ $ (1\ \le\ i\ \le\ N\ -\ 1) $ ただし、答えは非常に大きくなることがあるので、答えを $ 998244353 $ で割った余りを求めてください。

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

答えを $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 1000 $ - $ 1\ \leq\ M\ \leq\ 5000 $ - $ 0\ \leq\ K\ \leq\ M-1 $ - 入力は全て整数 ### Sample Explanation 1 条件を満たす数列は以下の $ 6 $ つです。 - $ (1,2) $ - $ (1,3) $ - $ (2,1) $ - $ (2,3) $ - $ (3,1) $ - $ (3,2) $ ### Sample Explanation 2 条件を満たす数列は以下の $ 2 $ つです。 - $ (1,3,1) $ - $ (3,1,3) $ ### Sample Explanation 3 答えを $ 998244353 $ で割った余りを出力してください。