Avito Cool Challenge 2018 C. Colorful Bricks 【排列组合】

传送门：http://codeforces.com/contest/1081/problem/C

C. Colorful Bricks

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

There are nn bricks lined in a row on the ground. Chouti has got mm paint buckets of different colors at hand, so he painted each brick in one of those mm 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 kk 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 998244353998244353.

Input

The first and only line contains three integers nn, mm and kk (1≤n,m≤2000,0≤k≤n−11≤n,m≤2000,0≤k≤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 998244353998244353.

Examples

input

Copy

3 3 0

output

Copy

3

input

Copy

3 2 1

output

Copy

4

Note

In the first example, since k=0k=0, the color of every brick should be the same, so there will be exactly m=3m=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 44 possible colorings.

题意概括：

N 个 方块， M 种颜色，存在 K 个方块使得它与相邻左边的方块颜色不同。

求涂色方案数。

解题思路：

换角度思考，其实就是 求把 N块方块分成 K+1块与相邻左边涂色不同的方案数。

杨辉三角求组合数 C(N-1, K), 因为第一块不考虑与左边颜色的关系 有 M 种可能，其余的都要去掉左边那一块的颜色，所以只有 M-1种可能，即 M*（M-1）*（M-1）*......*(M-1) ;

分块方案数 * 颜色方案数 即最后答案。

AC code：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int MAXN = 2e3+10;
const LL MOD = 998244353;
LL c[MAXN][MAXN];

LL qpow(LL x, LL n)
{
    LL res = 1LL;
    while(n){
        if(n&1) res = ((res%MOD*x%MOD)+MOD)%MOD;
        x = x*x%MOD;
        n>>=1LL;
    }
    return res;
}

int main()
{
    LL N, M, K;
    cin >> N >> M >> K;
    //memset(c, 1LL, sizeof(1LL));
    c[0][0] = c[1][0] = c[1][1] = 1LL;

    for(int i = 2; i <= N; i++){
        c[i][0] = 1LL;
        for(int j = 1; j < i; j++){
            c[i][j] = (c[i-1][j-1] + c[i-1][j])%MOD;
        }
        c[i][i] = 1LL;
    }

    //cout << c[N-1][K];

    LL ans = 1LL;
    ans = (M%MOD*c[N-1][K]%MOD*qpow(M-1LL, K)%MOD + MOD)%MOD;
    cout << ans << endl;
    return 0;

}