Problem

There are $ M $ type characters. Use them to create a string of length $ N $. How many strings are used that have $ K $ or more? Find too much divided by $ 998244353 $.

Here, the difference between two strings of length $ N $ is defined as follows.

* If the two strings are $ S = S_1S_2 \ ldots S_N $, $ T = T_1T_2 \ ldots T_N $, then $ i $$ (1 \ leq i \ leq N) becomes $ S_i \ neq T_i $ ) $ Exists.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq M \ leq 10 ^ {18} $
* $ 1 \ leq N \ leq 10 ^ {18} $
* $ 1 \ leq K \ leq 1000 $
* All inputs are integers

Input

The input is given in the following format.


$ M $ $ N $ $ K $


$ M, N, K $ are given on one line, separated by blanks.

Output

Output the remainder of the number of characters used in a string of length $ N $ that is greater than or equal to $ K $ divided by $ 998244353 $.

Examples

Input

2 10 1


Output

1024


Input

1 1 2


Output

0


Input

5 10 3


Output

9755400


Input

7 8 3


Output

5759460


Input

1000000000000000000 1000000000000000000 1000


Output

133611974
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 998244353 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

vector<ll> factmemo, factmemoInv;
ll factmemoMod = -1;

ll factorial(int n, int M){
  if(factmemoMod == M) return factmemo[n];
  if(n <= 1) return 1;

  ll res = 1;
  for(int i=1; i<=n; i++) res = res * i % M;
  return res;
}

ll power(ll k, ll n, int M){
  k %= M;
  if(n == 0) return 1;
  if(n == 1) return (ll)k;

  ll res = power(k, n/2, M);

  res = res * res % M;
  return n%2 == 1 ? res * k % M : res;
}

void initFactorial(int n, int M){
  factmemo.assign(n+1, 0);
  factmemoInv.assign(n+1, 0);
  factmemoMod = M;
  factmemo[0] = 1;
  for(int i=1;i<=n;i++) factmemo[i] = factmemo[i-1] * i % M;
  factmemoInv[n] = power(factmemo[n], M-2, M);
  for(int i=n;i>0;i--) factmemoInv[i-1] = factmemoInv[i] * i % M;
}

//nCm nPm nHm (mod M)

/*Combination*/
ll C(int n, int m, int M){
  if(n < m) return 0;
  if(m == 0 || n == m) return 1;

  if(factmemoMod == M)
    return factmemo[n] * factmemoInv[m] % M * factmemoInv[n-m] % M;

  ll numer = factorial(n, M);
  ll denom = factorial(m, M) * factorial(n-m, M) % M;

  denom = power((int)denom, M-2, M);

  return numer * denom % M;
}
/*Permutation*/
ll P(int n, int m, int M){
  if(n < m) return 0;
  if(m == 0) return 1;

  if(factmemoMod == M)
    return factmemo[n] * factmemoInv[n-m] % M;

  ll numer = factorial(n, M);
  ll denom = factorial(n-m, M);

  denom = power((int)denom, M-2, M);

  return numer * denom % M;
}
/*Combination with Repetitions*/
ll H(int n, int m, int M){
  if(n == 0 && m == 0) return 1;
  return C(n+m-1, m, M);
}

ll Mfactk[1010], factk[1010], factkInv[1010];

int main(){
  ll M, N, K;

  cin >> M >> N >> K;

  ll ans = 0;

  if (K > M) {
    puts("0");
    return 0;
  }

  Mfactk[0] = M % mod;
  factk[0] = 1;
  for(int i=1; i<=K; i++) {
    factk[i]  = factk[i-1] * i % mod;
    Mfactk[i] = Mfactk[i-1] * ((M - i) % mod) % mod;
  }

  for(int i=0; i<=K; i++) {
    factkInv[i] = power(factk[i], mod-2, mod);
  }

  ll v[1010];

  for(int i=1; i<K; i++) {
    v[i] = 0;

    ll fact = i;

    for(int j=1; j<=i; j++) {
      ll add = power(j, N, mod) * fact % mod * factkInv[j] % mod;
      fact = fact * (i - j) % mod;
      v[i] = (v[i] + mod + add * ((i - j) % 2 ? -1 : 1)) % mod;
    }

    //debug(i);
    //debug(v[i]);
  }

  /*
  for(int i=1; i<K; i++) {
    ll add = power(i, N, mod) * Mfactk[i-1] % mod * factkInv[i] % mod;
    debug(add);
    debug(power(i, N, mod));
    debug(Mfactk[i-1] * factkInv[i] % mod);
    debug(C(M, i, mod));
    ans = (ans + mod + add * (i % 2 ? -1 : 1)) % mod;
  }
  */

  for(int i=1; i<K; i++) {
    ll add = Mfactk[i-1] * factkInv[i] % mod * v[i];
    ans = (ans + add) % mod;
  }

  debug(ans);

  ans = (power(M, N, mod) + mod - ans) % mod;

  cout << ans << endl;

  return 0;
}

