#include <bits/stdc++.h>
using namespace std;
const int MOD = (119 << 23) + 1, root = 3;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = 4 * atan((long double)1);
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(long double& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = cd(a, b);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = (0); i < ((int)a.size()); ++i) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = (0); i < (SZ); ++i) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { pr("]\n"); }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace output
using namespace output;
namespace io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  cin.sync_with_stdio(0);
  cin.tie(0);
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace io
using namespace io;
typedef decay<decltype(MOD)>::type T;
struct mi {
  T val;
  explicit operator T() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-MOD <= v && v <= MOD) ? v : v % MOD;
    if (val < 0) val += MOD;
  }
  friend void pr(const mi& a) { pr(a.val); }
  friend void re(mi& a) {
    long long x;
    re(x);
    a = mi(x);
  }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % MOD;
    return *this;
  }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a != 0);
    return pow(a, MOD - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
int size(int second) { return second > 1 ? 32 - __builtin_clz(second - 1) : 0; }
void genRoots(vector<complex<double> >& roots) {
  int n = (int)roots.size();
  double ang = 2 * PI / n;
  for (int i = (0); i < (n); ++i)
    roots[i] = complex<double>(cos(ang * i), sin(ang * i));
}
void genRoots(vector<mi>& roots) {
  int n = (int)roots.size();
  mi r = pow(mi(root), (MOD - 1) / n);
  roots[0] = 1;
  for (int i = (1); i < (n); ++i) roots[i] = roots[i - 1] * r;
}
template <class T>
void fft(vector<T>& a, const vector<T>& roots, bool inv = 0) {
  int n = (int)a.size();
  for (int i = 1, j = 0; i < n; i++) {
    int bit = n >> 1;
    for (; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) swap(a[i], a[j]);
  }
  for (int len = 2; len <= n; len <<= 1)
    for (int i = 0; i < n; i += len)
      for (int j = (0); j < (len / 2); ++j) {
        int ind = n / len * j;
        if (inv && ind) ind = n - ind;
        auto u = a[i + j], v = a[i + j + len / 2] * roots[ind];
        a[i + j] = u + v, a[i + j + len / 2] = u - v;
      }
  if (inv) {
    T i = T(1) / T(n);
    for (auto& x : a) x *= i;
  }
}
template <class T>
vector<T> mult(vector<T> a, vector<T> b) {
  if (!min((int)a.size(), (int)b.size())) return {};
  int second = (int)a.size() + (int)b.size() - 1, n = 1 << size(second);
  vector<T> roots(n);
  genRoots(roots);
  a.resize(n), fft(a, roots);
  b.resize(n), fft(b, roots);
  for (int i = (0); i < (n); ++i) a[i] *= b[i];
  fft(a, roots, 1);
  a.resize(second);
  return a;
}
vector<int> invs, fac, ifac;
void genFac(int SZ) {
  invs.resize(SZ), fac.resize(SZ), ifac.resize(SZ);
  invs[1] = fac[0] = ifac[0] = 1;
  for (int i = (2); i < (SZ); ++i)
    invs[i] = MOD - (long long)MOD / i * invs[MOD % i] % MOD;
  for (int i = (1); i < (SZ); ++i) {
    fac[i] = (long long)fac[i - 1] * i % MOD;
    ifac[i] = (long long)ifac[i - 1] * invs[i] % MOD;
  }
}
long long comb(int a, int b) {
  if (a < b || b < 0) return 0;
  return (long long)fac[a] * ifac[b] % MOD * ifac[a - b] % MOD;
}
int n, m, k;
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  re(n, m, k);
  int hi = min(n, k);
  genFac(hi + 1);
  vector<mi> a, b;
  for (int i = (0); i < (hi + 1); ++i) {
    mi z = ifac[i];
    if (i & 1) z *= -1;
    a.push_back(z);
  }
  for (int i = (0); i < (hi + 1); ++i) {
    b.push_back(pow(mi(i), k) * ifac[i]);
  }
  auto c = mult(a, b);
  mi cur = 1, ans = 0;
  for (int i = (1); i < (hi + 1); ++i) {
    cur *= n + 1 - i;
    cur /= m;
    ans += cur * c[i];
  }
  ps(ans);
}

### Prompt

Your task is to create a Cpp solution to the following problem:

Consider the following experiment. You have a deck of m cards, and exactly one card is a joker. n times, you do the following: shuffle the deck, take the top card of the deck, look at it and return it into the deck.

Let x be the number of times you have taken the joker out of the deck during this experiment. Assuming that every time you shuffle the deck, all m! possible permutations of cards are equiprobable, what is the expected value of x^k? Print the answer modulo 998244353.

Input

The only line contains three integers n, m and k (1 ≤ n, m < 998244353, 1 ≤ k ≤ 5000).

Output

Print one integer — the expected value of x^k, taken modulo 998244353 (the answer can always be represented as an irreducible fraction a/b, where b mod 998244353 ≠ 0; you have to print a ⋅ b^{-1} mod 998244353).

Examples

Input


1 1 1


Output


1


Input


1 1 5000


Output


1


Input


2 2 2


Output


499122178


Input


998244352 1337 5000


Output


326459680

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = (119 << 23) + 1, root = 3;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = 4 * atan((long double)1);
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(long double& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = cd(a, b);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = (0); i < ((int)a.size()); ++i) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = (0); i < (SZ); ++i) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { pr("]\n"); }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace output
using namespace output;
namespace io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  cin.sync_with_stdio(0);
  cin.tie(0);
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace io
using namespace io;
typedef decay<decltype(MOD)>::type T;
struct mi {
  T val;
  explicit operator T() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-MOD <= v && v <= MOD) ? v : v % MOD;
    if (val < 0) val += MOD;
  }
  friend void pr(const mi& a) { pr(a.val); }
  friend void re(mi& a) {
    long long x;
    re(x);
    a = mi(x);
  }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % MOD;
    return *this;
  }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a != 0);
    return pow(a, MOD - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
int size(int second) { return second > 1 ? 32 - __builtin_clz(second - 1) : 0; }
void genRoots(vector<complex<double> >& roots) {
  int n = (int)roots.size();
  double ang = 2 * PI / n;
  for (int i = (0); i < (n); ++i)
    roots[i] = complex<double>(cos(ang * i), sin(ang * i));
}
void genRoots(vector<mi>& roots) {
  int n = (int)roots.size();
  mi r = pow(mi(root), (MOD - 1) / n);
  roots[0] = 1;
  for (int i = (1); i < (n); ++i) roots[i] = roots[i - 1] * r;
}
template <class T>
void fft(vector<T>& a, const vector<T>& roots, bool inv = 0) {
  int n = (int)a.size();
  for (int i = 1, j = 0; i < n; i++) {
    int bit = n >> 1;
    for (; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) swap(a[i], a[j]);
  }
  for (int len = 2; len <= n; len <<= 1)
    for (int i = 0; i < n; i += len)
      for (int j = (0); j < (len / 2); ++j) {
        int ind = n / len * j;
        if (inv && ind) ind = n - ind;
        auto u = a[i + j], v = a[i + j + len / 2] * roots[ind];
        a[i + j] = u + v, a[i + j + len / 2] = u - v;
      }
  if (inv) {
    T i = T(1) / T(n);
    for (auto& x : a) x *= i;
  }
}
template <class T>
vector<T> mult(vector<T> a, vector<T> b) {
  if (!min((int)a.size(), (int)b.size())) return {};
  int second = (int)a.size() + (int)b.size() - 1, n = 1 << size(second);
  vector<T> roots(n);
  genRoots(roots);
  a.resize(n), fft(a, roots);
  b.resize(n), fft(b, roots);
  for (int i = (0); i < (n); ++i) a[i] *= b[i];
  fft(a, roots, 1);
  a.resize(second);
  return a;
}
vector<int> invs, fac, ifac;
void genFac(int SZ) {
  invs.resize(SZ), fac.resize(SZ), ifac.resize(SZ);
  invs[1] = fac[0] = ifac[0] = 1;
  for (int i = (2); i < (SZ); ++i)
    invs[i] = MOD - (long long)MOD / i * invs[MOD % i] % MOD;
  for (int i = (1); i < (SZ); ++i) {
    fac[i] = (long long)fac[i - 1] * i % MOD;
    ifac[i] = (long long)ifac[i - 1] * invs[i] % MOD;
  }
}
long long comb(int a, int b) {
  if (a < b || b < 0) return 0;
  return (long long)fac[a] * ifac[b] % MOD * ifac[a - b] % MOD;
}
int n, m, k;
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  re(n, m, k);
  int hi = min(n, k);
  genFac(hi + 1);
  vector<mi> a, b;
  for (int i = (0); i < (hi + 1); ++i) {
    mi z = ifac[i];
    if (i & 1) z *= -1;
    a.push_back(z);
  }
  for (int i = (0); i < (hi + 1); ++i) {
    b.push_back(pow(mi(i), k) * ifac[i]);
  }
  auto c = mult(a, b);
  mi cur = 1, ans = 0;
  for (int i = (1); i < (hi + 1); ++i) {
    cur *= n + 1 - i;
    cur /= m;
    ans += cur * c[i];
  }
  ps(ans);
}

```