#include <bits/stdc++.h> using namespace std; using LL = long long; const int MAXN = 3003; const int MOD = 1000000007; LL n, m; LL dp[MAXN][MAXN][2]; int power(long long x, unsigned int y) { int res = 1; x = x % MOD; if (x == 0) return 0; while (y > 0) { if (y & 1) res = (res*x) % MOD; y = y>>1; x = (x*x) % MOD; } return res; } LL depe(LL n, LL k, bool b) { if (k > m) { return 0; } if (n == 0) { return 1; } if (dp[n][k][b] != -1) { return dp[n][k][b]; } if (b == 0) { int x = depe(n - 1, k, 0) * max(0LL, (m - k)) % MOD; int y = depe(n - 1, k, 1) * k % MOD; int sum = (x + y) % MOD; dp[n][k][b] = sum; } else { int x = depe(n - 1, k, 1) * k % MOD; int y = depe(n - 1, k + 1, 0) * max(0LL, (m - k - 1LL)) % MOD; int sum = (x + y) % MOD; dp[n][k][b] = sum; } // cout << "depe " << n << " " << k << " " << b << " " << dp[n][k][b] << endl; return dp[n][k][b]; } int main() { cin >> n >> m; if (n == 1) { cout << 0 << endl; return 0; } if (n == 2) { cout << m << endl; return 0; } memset(dp, -1, sizeof(dp)); int sum = depe(n - 2, 1, 0); LL mpo2 = (m * (m - 1) / 2) % MOD; mpo2 *= 2; mpo2 %= MOD; LL res = power(m, n - 2) - sum; if (res < 0) { res += MOD; } res *= mpo2; res %= MOD; LL pom = m * (LL)power(m, n - 2) % MOD; res += pom; res %= MOD; cout << res << endl; }
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 | #include <bits/stdc++.h> using namespace std; using LL = long long; const int MAXN = 3003; const int MOD = 1000000007; LL n, m; LL dp[MAXN][MAXN][2]; int power(long long x, unsigned int y) { int res = 1; x = x % MOD; if (x == 0) return 0; while (y > 0) { if (y & 1) res = (res*x) % MOD; y = y>>1; x = (x*x) % MOD; } return res; } LL depe(LL n, LL k, bool b) { if (k > m) { return 0; } if (n == 0) { return 1; } if (dp[n][k][b] != -1) { return dp[n][k][b]; } if (b == 0) { int x = depe(n - 1, k, 0) * max(0LL, (m - k)) % MOD; int y = depe(n - 1, k, 1) * k % MOD; int sum = (x + y) % MOD; dp[n][k][b] = sum; } else { int x = depe(n - 1, k, 1) * k % MOD; int y = depe(n - 1, k + 1, 0) * max(0LL, (m - k - 1LL)) % MOD; int sum = (x + y) % MOD; dp[n][k][b] = sum; } // cout << "depe " << n << " " << k << " " << b << " " << dp[n][k][b] << endl; return dp[n][k][b]; } int main() { cin >> n >> m; if (n == 1) { cout << 0 << endl; return 0; } if (n == 2) { cout << m << endl; return 0; } memset(dp, -1, sizeof(dp)); int sum = depe(n - 2, 1, 0); LL mpo2 = (m * (m - 1) / 2) % MOD; mpo2 *= 2; mpo2 %= MOD; LL res = power(m, n - 2) - sum; if (res < 0) { res += MOD; } res *= mpo2; res %= MOD; LL pom = m * (LL)power(m, n - 2) % MOD; res += pom; res %= MOD; cout << res << endl; } |