問題文

整数 N,M,K が与えられます．

長さ N の非負整数列 A=(A_1,A_2,\cdots,A_N) であって，以下の条件を両方満たすものをよい数列と呼ぶことにします．

• \sum_{1 \leq i \leq N}A_i=M
• A_1=K

よい数列 A に対して，f(A) を次のように定義します．

\[ f(A)=\prod_{1 \leq i \leq N-1} {A_i+A_{i+1} \choose A_i } \]

すべてのよい数列に対する f(A) の総和を 998244353 で割った余りを求めてください．

制約

• 2 \leq N \leq 250000
• 0 \leq K \leq M \leq 250000
• 入力される値はすべて整数．

入力例 1

3 2 1

出力例 1

3

よい数列は 2 通りあり，対応する f(A) の値は以下のとおりです．

• A=(1,0,1): f(A)={1 \choose 1} \times {1 \choose 0}=1

• A=(1,1,0): f(A)={2 \choose 1} \times {1 \choose 1}=2

よって答えは 1+2=3 です．

入力例 2

5 10 3

出力例 2

27670

入力例 3

100 0 0

出力例 3

1

入力例 4

100 1000 10

出力例 4

75806874