Submission #826334

---

Source Code Expand

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long LL;

LL powmod(LL a, int n){
	if(n == 0) return 1;
	if(n % 2) return (a*powmod(a,n-1)) % MOD;
	LL c = powmod(a,n/2);
	return (c*c) % MOD;
}
LL inv(LL a){
	return powmod(a,MOD-2);
}
LL dp[2100][2100];
LL fact[5000000];
LL invfact[5000000];
int main(){
	int n, k;
	cin >> n >> k;
	if(k == 1){
		cout << 1 << endl;
		return 0;
	}
	fact[0] = 1;
	for(LL i = 1; i <= 4010000; i++) fact[i] = (fact[i-1]*i) % MOD;
	invfact[4010000] = inv(fact[4010000]);
	for(LL i = 4010000-1; i >= 0; i--) invfact[i] = (invfact[i+1] * (i+1)) % MOD;

	dp[0][0] = 1;
	for(int a = 1; a <= n; a++){
		for(int b = a; b >= 0; b--){
			LL r = 0;
			if(b > 0){
				r = (a*fact[a*k-b-1]) % MOD;
				r = (r*invfact[k-2]) % MOD;
				r = (r*invfact[a*k-b-1 - (k-2)]) % MOD;
				r = (r*dp[a-1][b-1]) % MOD;
			}
			r = (r + dp[a][b+1]) % MOD;
			dp[a][b] = r;
		}
	}
	cout << dp[n][0] % MOD << endl;
}

Submission Info

Judge Result