あなたは、いくつかの種類の賞品が当たるチャリティー抽選会に参加しています。この抽選会は少し変わった方法で行われます。抽選券を1枚使うと、異なる種類の賞品が2つランダムに選ばれます。しかし、両方をもらえるわけではなく、その2つのうちどちらか一方を選ばなければなりません。
あなたは一定数の抽選券を持っています。すべての抽選券を使い切り、同じ数の賞品を獲得します。同じ種類の賞品をあまり多く持ちたくないため、2つの賞品から選ぶ際は、これまでに獲得した数が少ない方の賞品を選びます。2つの賞品の獲得数が同じ場合（両方とも0の場合を含む）は、賞品の種類番号が小さい方を選びます。
上記のような戦略をとっても、同じ種類の賞品を過剰に獲得してしまうことを避けられるとは限りません。ある種類の賞品の獲得数が一定の制限を超えると、あなたは不満を感じます。すべての抽選券を使い切った後、不満を感じないような賞品の組み合わせが何通りあるかを求めてください。賞品の組み合わせは、少なくとも1種類の賞品の個数が異なれば、異なる組み合わせとみなします。どの種類の賞品も無制限に供給されているものと仮定して構いません。
入力
入力は以下の形式の単一のテストケースで構成されます。
$n$ $k$ $m$
最初の整数 $n$ ($2 \le n \le 10^6$) は賞品の種類数です。2番目の整数 $k$ ($1 \le k \le 10^6$) は持っている抽選券の枚数です。3番目の整数 $m$ ($1 \le m \le k$) は、不満を感じないための、単一の種類の賞品の最大獲得数です。
出力
不満を感じないような賞品の組み合わせの数を、素数である 998 244 353 で割った余りを出力してください。
入出力例
入力 1
3 1 1
出力 1
2
入力 2
3 3 2
出力 2
4
入力 3
3 3 1
出力 3
1
入力 4
2025 1207 64
出力 4
660312977
注記
入力例 1 では、1番目または2番目の種類の賞品を獲得しますが、3番目の賞品は獲得しません。
入力例 2 では、以下の4通りの賞品の組み合わせが可能です。いずれの場合も、どの種類の賞品の数も $m = 2$ 以下であるため、不満を感じることはありません。
- 1番目の賞品2つと2番目の賞品1つ
- 1番目の賞品2つと3番目の賞品1つ
- 2番目の賞品2つと3番目の賞品1つ
- 3種類の賞品をそれぞれ1つずつ
入力例 3 では、上記の4つの組み合わせのうち、どの種類の賞品も1つを超えないのは最後の組み合わせのみです。