After solving the problem Gem Island from the ACM-ICPC World Finals 2018, Little Cyan Fish thinks that this problem is too easy. Luckily, Little Cyan Fish’s good friend, Little DrinkDrinkCongee, prepared the following problem for him. So he would like to solve the following problem.

There are $n$ boxes in a row. Initially there is exactly one ball in each box. You will perform the following operation exactly $d$ times:

• Choose a ball $x$ from all the balls uniformly at random.
• Assume the ball $x$ is in the box $b$, add one more ball to the box $b$.

Apparently, during the $i$-th operation, each ball has a probability of $\frac{1}{n+i-1}$ to be chosen. Suppose that after $d$ operations the numbers of balls in these $n$ boxes are listed in non-increasing order as $a_1 \geq a_2 \geq \dots \geq a_n$. Find the expected value of $\sum_{i=1}^r a_i$, modulo $998\,244\,353$.

Since the problem is too hard for Little Cyan Fish, he asked you to help him to solve this problem.

Input

The first line of the input contains three integers $n$, $d$ and $r$ ($1 \leq n, d \leq 1.5 \times 10^7$, $1 \leq r \leq n$).

Output

Output a single line contains a single integer, indicating the answer modulo $998\,244\,353$.

Examples

Input 1

2 3 1

Output 1

499122180

Input 2

3 3 2

Output 2

698771052

Input 3

5 10 3

Output 3

176512750