Expected Value of Card Draw Exponentiation

You are given m cards, among which one is a special card (joker). You shuffle all the cards uniformly at random n times. In each shuffle, record whether the first card is the joker. Let x be the number of shuffles in which the first card is the joker. You are also given an integer k. Your task is to compute the expected value of x^k modulo 998244353.

In other words, if in each shuffle the probability that the first card is the joker is \(\frac{1}{m}\), then \(x\) follows a Binomial distribution with parameters \(n\) and \(\frac{1}{m}\). The problem asks to compute:

[ E\left[x^k\right]=\sum_{x=0}^{n}x^k \cdot \binom{n}{x}\left(\frac{1}{m}\right)^x \left(\frac{m-1}{m}\right)^{n-x} \quad \text{mod }998244353. ]

It can be shown that using Stirling numbers of the second kind \(S(k,j)\) one may express the k-th moment as:

[ E\left[x^k\right]=\sum_{j=1}^{\min(k,n)}S(k,j)\cdot \frac{n(n-1)\cdots (n-j+1)}{m^j} \quad \text{mod }998244353. ]

Output the answer modulo 998244353.

inputFormat

The input consists of a single line containing three space‐separated integers:

• m — the total number of cards,
• n — the number of shuffles,
• k — the exponent in the expression.

outputFormat

Output a single integer which is the value of \(E[x^k]\) modulo 998244353.

sample

2 3 1

499122178