G. Gem Island 2
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \cdots \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
2 3 1
Output
499122180
Input
3 3 2
Output
698771052
Input
5 10 3
Output
176512750