Atcoder
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 4000010, mod = 1e9 + 7; int n, k, fact[N], invf[N], f[2010][2010]; int qmi(int a, int b) { int res = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod; return res; } int inv(int x) { return qmi(x, mod - 2); } int C(int n, int m) { return 1ll * fact[n] * invf[m] % mod * invf[n - m] % mod; } int main() { cin >> n >> k; fact[0] = 1, invf[0] = 1; if (k == 1) return cout << "1" << endl, 0; for (int i = 1; i <= 4000000; i++) fact[i] = 1ll * fact[i - 1] * i % mod, invf[i] = inv(fact[i]); for (int i = 0; i <= n; i++) f[i][0] = 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) f[i][j] = (f[i - 1][j] + 1ll * f[i][j - 1] * (n - j + 1) % mod * C(n * k - i - 1 - (j - 1) * (k - 1), k - 2) % mod) % mod; cout << f[n][n] << endl; return 0; }