1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <bits/stdc++.h>
using namespace std;
long long n, m, res, t[3001][1501];
const long long MOD = 1e9 + 7;

long long powmod(long long a, long long p) {
  long long res = 1, k = a;
  while (p > 0) {
    if (p % 2) {
      res = (res * k) % MOD;
    }
    k = (k * k) % MOD;
    p >>= 1;
  }
  return res % MOD;
}

long long f(int dl, int l) {
  if (t[dl][l] != 0) {
    return t[dl][l];
  }

  if (l >= m) {
    t[dl][l] = 0;
    return 0;
  }

  // cout << "t[" << dl << "]["<< l << "]" << endl;

  if (m - 2 - l > 0) {
    for (int i = 0; i <= dl - 2; i++) {
      long long fs = f(dl - i - 2, l + 1);
      if (fs == 0) {
        break;
      }
      if (i < dl - 2) {
        fs *= (m - 2 - l);
        fs %= MOD;
      }
      t[dl][l] += (powmod(m - 1 - l, i) * fs) % MOD;
      // cout << "   (m - 2 - l) " << m - 2 - l << " dla i " << i << " " << pow(m - 1 - l, i) << " * " << fs << " = " << (powmod(m - 1 - l, i) * fs) % MOD << endl;
      t[dl][l] %= MOD;
    }
    t[dl][l] *= m - 2 - l;
    t[dl][l] %= MOD;
  }
  if (dl > 1) {
    t[dl][l] += pow(m - 1 - l, dl - 1) - 1;
    t[dl][l] %= MOD;
    // cout << "  (+ " << pow(m - 1 - l, dl - 1) - 1 << ") czyli do końca są 1" << endl;
  }

  // cout << "     " << t[dl][l] << " + " << dl << " + " << pow(m - l - 1, dl) << endl;


  t[dl][l] += dl;
  t[dl][l] %= MOD;
  t[dl][l] += pow(m - l - 1, dl);
  t[dl][l] %= MOD;

  // cout << "   t[" << dl << "]["<< l << "] = " << t[dl][l] << endl;
  return t[dl][l];
}

int main()
{
  ios_base::sync_with_stdio(0);

  cin >> n >> m;
  if (m == 1) {
    cout << 1 << endl;
    return 0;
  }
  if (n == 1) {
    cout << 0 << endl;
    return 0;
  }

  long long mn = m;

  for (int i = 1; i < n; i++) {
    t[0][i] = 1;
    mn *= m;
    mn %= MOD;
  }

  res = f(n - 2, 0) * m;
  res %= MOD;
  res *= m - 1;
  res %= MOD;

  // cout << mn << " - (" << f(n - 2, 0) << " * " << m << " * " << m - 1 << ")" << endl;

  res = mn - res;
  if (res < 0) {
    res += MOD;
  }
  cout << res << endl;

  return 0;
}