AT_kupc2020_m Many Parentheses

[problemUrl]: https://atcoder.jp/contests/kupc2020/tasks/kupc2020_m 括弧列は、`(` と `)` からなる文字列です。 正しい括弧列を、次のいずれかの条件を満たすものと定義します。 - 空文字列 - 正しい括弧列 $ A $ が存在し、`(` , $ A $ , `)` をこの順に結合した文字列 - 空でない正しい括弧列 $ S,T $ が存在し、$ S $ , $ T $ をこの順に結合した文字列 いま、$ N $ 個の互いに区別できる箱があります。 あなたは $ N $ 個の箱それぞれに正しい括弧列を入れようと考えています。ただし、次の2つの条件をともに満たすように入れる必要があります。 - $ N $ 個の箱に含まれる `(` の個数の合計が $ M $ になる。 - 長さが $ 2\ \times\ K $ である括弧列はどの箱にも入れてはならない。 条件を満たす入れ方の総数を $ 998244353 $ で割ったあまりを求めてください。 ただし、$ 2 $ つの入れ方が異なることを、「ある箱が存在し、そこに入れた括弧列が異なること」と定義します。

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

答えを1行に出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^6 $ - $ 1\ \leq\ M\ \leq\ 10^6 $ - $ 1\ \leq\ K\ \leq\ M $ ### 部分点 - $ 1\ \leq\ N,M\ \leq\ 2000 $ を満たすデータセットに正解した場合は、$ 10 $ 点が与えられる。 - 追加制約のないデータセットに正解した場合は、上記とは別に $ 490 $ 点が与えられる。 ### Sample Explanation 1 \- `(())` , 空 - `()()` , 空 - 空 , `(())` - 空 , `()()` の $ 4 $ 通りです。