D. Pandemic
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Kanade's university was recently forced to close due to a pandemic. The students were locked in the dormitory building and were not allowed to go out. But fortunately, the university has prepared abundant free meals for them. While enjoying the considerate service, the students also volunteer enthusiastically, contributing their modest efforts to the university's work. Kanade is no exception.

Kanade's job is to distribute boxed lunches to the students in $$$n$$$ rooms numbered from $$$1$$$ to $$$n$$$, which are continuously arranged from left to right on a corridor, with $$$4$$$ students in each room. The school provides $$$m$$$ different kinds of boxed meals, each of which is sufficiently provided (meaning they are infinite).

Kanade decided to distribute the boxed lunches to the rooms from left to right. Specifically, the $$$i$$$-th distribution is to randomly take out $$$4$$$ boxed lunches from the boxed lunch chest and send it to the $$$i$$$-th room. A few days later however, Kanade found it exhausting to rush back and forth in the building and knock the door from room to room, so he came up with a more relaxing way.

The order is still left-to-right, but the $$$i$$$-th distribution is to randomly take $$$4k_i$$$ boxed lunches from the chest, and knock the doors of $$$k_i$$$ continuous room(s) starting from the first room from left to right that hasn't been distributed. He will then put the $$$4k_i$$$ boxed lunches on the floor for the students from the $$$k_i$$$ room(s) to choose. The process will continue until all the $$$n$$$ rooms are distributed. Each $$$k_i$$$ is a positive integer that Kanade can decide, but he doesn't want $$$k_i$$$ to be too large to cause unnecessary confusion, so he stipulated that $$$k_i \leq K$$$.

Kanade wonders how many different plans there are to distribute the boxed lunches in such way. Two plans are considered different if and only if the times of distribution are different, $$$k_i$$$ for the $$$i$$$-th distribution are different, or the number of any kind of boxed lunch taken out in $$$i$$$-th distribution are different.

Since this number may be too large, output it modulo $$$998244353$$$.

Input

There is only one line, which contains three positive integer numbers $$$n, m, K\ (1\leq K \leq n \leq 10^5, 1\leq m\leq 10^5)$$$ — the number of rooms, the number of the types of boxed meals, and the upper bound of rooms that Kanade can distribute in each distribution.

Output

Output a single number — the number of different distributing plans modulo $$$998244353$$$.

Examples
Input
3 1 2
Output
3
Input
3 2 1
Output
125
Input
10 4 3
Output
559774277
Note

Note that what Kanade wonders is the number of different distributing plans, meaning that he doesn't care how the students divide the $$$4k_i$$$ boxed lunches in the $$$i$$$-th distribution.