P5401 [CTS2019] Pearls

Time passes and everything changes. In front of Baiyun, only a blurred scene remains. In the vague view, it saw many small pearls, some shining with colorful light. These pearls were left by the white rabbit. Each pearl has a color, randomly chosen from $D$ colors. Baiyun wants to put these pearls into some small bottles. Each bottle can hold exactly two pearls. It also has requirements: every bottle must be full, and the two pearls in it must have the same color. Baiyun hopes to obtain at least $m$ full bottles of pearls, and it wants to know the probability that its wish can be achieved.

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.

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

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

#### 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