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
#include <bits/stdc++.h>

using namespace std;

typedef long long lld;

constexpr int INF = 1e9+7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int> > dp(n, vector<int> (n / 2 + 1, 0));

    dp[1][1] = m;
    for (int i = 2; i < n; ++i)
      for (int k = 1; k <= n / 2; ++k)
        dp[i][k] = ((lld)dp[i - 1][k] * (lld)m + (lld)dp[i - 2][k - 1] * (lld)(m - k + 1)) % (lld)INF; // 2*10^18 

    int sum = 0;
    for (int i = 0; i <= n / 2; ++i)
      sum = ((lld)sum + (lld)dp.back()[i]) % (lld)INF;
    cout << sum << '\n';
}