Description

There are $n$ independent uniformly random integer variables in the range $[1,D]$.

Find the probability that we can choose at least $m$ bottles, such that there exists a way to select some variables and put each selected variable into a bottle, satisfying that each bottle contains exactly two variables with the same value.

Output the value of the probability multiplied by $D^n$, taken modulo $998244353$. For the modulo details, refer to Problem 1.

Input Format

The input contains only one line with three integers $D,n,m$ separated by spaces.

Output Format

Output one integer, representing the required value of the probability multiplied by $D^n$ modulo $998244353$.

2 2 1

2

8 10 4

301103104

998 1000 500

762913089

Hint

Sample 1 Explanation

Case $1$: the first variable is $1$, and the second variable is $1$.

Case $2$: the first variable is $1$, and the second variable is $2$.

Case $3$: the first variable is $2$, and the second variable is $1$.

Case $4$: the first variable is $2$, and the second variable is $2$.

In cases $1$ and $4$, we can put the two variables into one bottle.

In cases $2$ and $3$, the two variables have different values, so they cannot be put into the same bottle.

Testdata Convention

All test points satisfy $0 \leqslant m \leqslant 10^9,1 \leqslant n \leqslant 10^9,1 \leqslant D \leqslant 10^5$。

Translated by ChatGPT 5