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 1

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