Score : $500$ points

Problem Statement

Takahashi is playing sugoroku, a board game.

The board has $N+1$ squares, numbered $0$ to $N$. Takahashi starts at square $0$ and goes for square $N$.

The game uses a roulette wheel with $M$ numbers from $1$ to $M$ that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square $N$, he turns around at square $N$ and goes back by the excessive number of squares.

For instance, assume that $N=4$ and Takahashi is at square $3$. If the wheel shows $4$, the excessive number of squares beyond square $4$ is $3+4-4=3$. Thus, he goes back by three squares from square $4$ and arrives at square $1$.

When Takahashi arrives at square $N$, he wins and the game ends.

Find the probability, modulo $998244353$, that Takahashi wins when he may spin the wheel at most $K$ times.

Constraints

• $M \leq N \leq 1000$
• $1 \leq M \leq 10$
• $1 \leq K \leq 1000$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$ $K$

Output

Print the answer.

2 2 1

499122177

Takahashi wins in one spin if the wheel shows $2$. Therefore, the probability of winning is $\frac{1}{2}$.

We have $2\times 499122177 \equiv 1 \pmod{998244353}$, so the answer to be printed is $499122177$.

10 5 6

184124175

100 1 99

0