There are $n$ independent random variables, each uniformly distributed in the range $[1, D]$.
Find the probability that at least $m$ bottles can be filled, such that there exists a scheme to select some of the variables and place each selected variable into a bottle, satisfying the condition that each bottle contains exactly two variables with the same value.
Output the value of the probability multiplied by $D^n$, modulo $998244353$.
Input
The input consists of a single line containing three space-separated integers $D, n, m$.
Output
Output a single integer representing the probability multiplied by $D^n$, modulo $998244353$.
Examples
Input 1
2 2 1
Output 1
2
Note
Case 1: First variable is 1, second variable is 1. Case 2: First variable is 1, second variable is 2. Case 3: First variable is 2, second variable is 1. Case 4: First variable is 2, second variable is 2.
In cases 1 and 4, the two variables can be placed into one bottle. In cases 2 and 3, the values of the two variables are different, so they cannot be placed into the same bottle.
Input 2
pearl/pearl2.in
Output 2
pearl/pearl2.ans
Input 3
pearl/pearl3.in
Output 3
pearl/pearl3.ans
Constraints
For all test cases, $1 \le m \le n \le 10^9, 1 \le D \le 10^5$.
| Test Case | $D$ | $n$ | $m$ |
|---|---|---|---|
| 1 | .h=2 $D \le 2$ | $n \le 10$ | .h=15 $m \le n$ |
| 2 | $n \le 20$ | ||
| 3 | .h=5 $D \le 100$ | .h=5 $n \le 100$ | |
| 4 | |||
| 5 | |||
| 6 | |||
| 7 | |||
| 8 | .h=5 $D \le 4000$ | .h=5 $n \le 4000$ | |
| 9 | |||
| 10 | |||
| 11 | |||
| 12 | |||
| 13 | .h=3 $D \le 300$ | .h=13 $n \le 10^9$ | |
| 14 | |||
| 15 | |||
| 16 | .h=10 $D \le 10^5$ | $m \le 0$ | |
| 17 | $m \le 1$ | ||
| 18 | $m \le 2$ | ||
| 19 | .h=7 $m \le n$ | ||
| 20 | |||
| 21 | |||
| 22 | |||
| 23 | |||
| 24 | |||
| 25 |