Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Colorful Bricks

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOn his free time, Chouti likes doing some housework. He has got one new task, paint some bricks in the yard.

There are $$$n$$$ bricks lined in a row on the ground. Chouti has got $$$m$$$ paint buckets of different colors at hand, so he painted each brick in one of those $$$m$$$ colors.

Having finished painting all bricks, Chouti was satisfied. He stood back and decided to find something fun with these bricks. After some counting, he found there are $$$k$$$ bricks with a color different from the color of the brick on its left (the first brick is not counted, for sure).

So as usual, he needs your help in counting how many ways could he paint the bricks. Two ways of painting bricks are different if there is at least one brick painted in different colors in these two ways. Because the answer might be quite big, you only need to output the number of ways modulo $$$998\,244\,353$$$.

Input

The first and only line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n,m \leq 2000, 0 \leq k \leq n-1$$$) — the number of bricks, the number of colors, and the number of bricks, such that its color differs from the color of brick to the left of it.

Output

Print one integer — the number of ways to color bricks modulo $$$998\,244\,353$$$.

Examples

Input

3 3 0

Output

3

Input

3 2 1

Output

4

Note

In the first example, since $$$k=0$$$, the color of every brick should be the same, so there will be exactly $$$m=3$$$ ways to color the bricks.

In the second example, suppose the two colors in the buckets are yellow and lime, the following image shows all $$$4$$$ possible colorings.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/20/2021 14:11:50 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|