#include <stdio.h> const int MOD = 1000000007; int I[3001][1501][2]; int main() { int n, m; scanf("%d%d", &n, &m); I[0][0][1] = 1; for (int i = 1; i <= n; i++) for (int s = 1; s <= (i+1)/2; s++) { I[i][s][1] = ((long long)s * (I[i-1][s][0] + I[i-1][s][1])) % MOD; I[i][s][0] = ((long long)(m - s) * I[i-1][s][0] + (long long)(m - s + 1) * I[i-1][s-1][1]) % MOD; } int answer = 0; for (int s = 0; s <= (n+1)/2; s++) answer = (answer + I[n][s][1]) % MOD; printf("%d\n", answer); return 0; }
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 | #include <stdio.h> const int MOD = 1000000007; int I[3001][1501][2]; int main() { int n, m; scanf("%d%d", &n, &m); I[0][0][1] = 1; for (int i = 1; i <= n; i++) for (int s = 1; s <= (i+1)/2; s++) { I[i][s][1] = ((long long)s * (I[i-1][s][0] + I[i-1][s][1])) % MOD; I[i][s][0] = ((long long)(m - s) * I[i-1][s][0] + (long long)(m - s + 1) * I[i-1][s-1][1]) % MOD; } int answer = 0; for (int s = 0; s <= (n+1)/2; s++) answer = (answer + I[n][s][1]) % MOD; printf("%d\n", answer); return 0; } |