Problem Background

Clouds drift, seas change into mulberry fields.

Before the clouds lies only a blurred vision.

In the hazy appearance, it sees small pearls, some glowing with colorful lights. These pearls were left by a rabbit, each pearl having a color, randomly one of $D$ colors.

The cloud wants to put these pearls into small bottles, each bottle exactly holding two pearls. However, it has a requirement: each bottle must be filled, and both pearls in the same bottle must be of the same color.

The cloud hopes to obtain at least $m$ filled bottles. It wonders what the probability is that its wish can be fulfilled.

Problem Description

There are $n$ uniformly random variables within the range $[1, D]$.

Determine the probability that at least $m$ bottles can be chosen such that there exists a scheme to select some variables and place each selected variable into a bottle, satisfying that each bottle contains exactly two variables of the same value.

Output the value of this probability multiplied by $D^n$ modulo $998244353$. For the modulo part, refer to the first problem for instructions.

Input Format

The input consists of a single line with three integers $D, n, m$ separated by spaces.

Output Format

Output a single integer, representing the sought probability multiplied by $D^n$ modulo $998244353$.

Sample Input and Output

Sample Input #1

2 2 1

Sample Output #1

2

Sample Input #2

8 10 4

Sample Output #2

301103104

Sample Input #3

998 1000 500

Sample Output #3

762913089

Notes

Sample 1 Explanation

Case 1: The first variable is 1, the second variable is 1.

Case 2: The first variable is 1, the second variable is 2.

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

Case 4: The first variable is 2, the second variable is 2.

Among these, cases 1 and 4 can place both variables in one bottle.

In cases 2 and 3, the values of the two variables are different, so they cannot be placed in the same bottle.

Test Data Constraints

All test cases satisfy $0 \leq m \leq 10^9, 1 \leq n \leq 10^9, 1 \leq D \leq 10^5$.

见题面 Input 部分

见题面 Output 部分