問題文

括弧列は、( と ) からなる文字列です。 正しい括弧列を、次のいずれかの条件を満たすものと定義します。

• 空文字列
• 正しい括弧列 A が存在し、( , A , ) をこの順に結合した文字列
• 空でない正しい括弧列 S,T が存在し、S , T をこの順に結合した文字列

いま、N 個の互いに区別できる箱があります。

あなたは N 個の箱それぞれに正しい括弧列を入れようと考えています。ただし、次の2つの条件をともに満たすように入れる必要があります。

• N 個の箱に含まれる ( の個数の合計が M になる。
• 長さが 2 \times K である括弧列はどの箱にも入れてはならない。

条件を満たす入れ方の総数を 998244353 で割ったあまりを求めてください。

ただし、2 つの入れ方が異なることを、「ある箱が存在し、そこに入れた括弧列が異なること」と定義します。

制約

• 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 点が与えられる。

入力例 1

2 2 1

出力例 1

4

• (()) , 空
• ()() , 空
• 空 , (())
• 空 , ()()

の 4 通りです。

入力例 2

1 1 1

出力例 2

0

入力例 3

24 120 30

出力例 3

379268651