ACM-ICPC World Finals 2018 の問題「Gem Island」を解いた後、Little Cyan Fish はこの問題が簡単すぎると考えました。幸いなことに、Little Cyan Fish の良き友人である Little DrinkDrinkCongee が彼のために以下の問題を用意しました。そこで彼は、この問題を解きたいと考えています。

一列に並んだ $n$ 個の箱があります。最初、各箱にはちょうど 1 個のボールが入っています。以下の操作をちょうど $d$ 回行います。

• すべてのボールの中から、ボール $x$ を一様にランダムに選びます。
• ボール $x$ が入っている箱を $b$ とし、箱 $b$ にボールをもう 1 個追加します。

明らかに、$i$ 回目の操作において、各ボールが選ばれる確率は $\frac{1}{n+i-1}$ です。$d$ 回の操作の後、$n$ 個の箱に入っているボールの数を降順に並べたものを $a_1 \ge a_2 \ge \dots \ge a_n$ とします。$\sum_{i=1}^r a_i$ の期待値を $998\,244\,353$ で割った余りを求めてください。

この問題は Little Cyan Fish にとって難しすぎるため、彼はあなたにこの問題を解く手助けを求めました。

入力

入力の最初の行には、3 つの整数 $n, d, r$ ($1 \le n, d \le 1.5 \times 10^7$, $1 \le r \le n$) が含まれます。

出力

答えを $998\,244\,353$ で割った余りを、1 行で出力してください。

入出力例

入力 1

2 3 1

出力 1

499122180

入力 2

3 3 2

出力 2

698771052

入力 3

5 10 3

出力 3

176512750