Submission #1068253

---

Source Code Expand

//In the name of Allah 
#include <bits/stdc++.h>

using namespace std; 

#define F first
#define S second
#define MP make_pair
#define PB push_back
#define int long long

const int N=5e6+200;
const int NN=2e3+100;
const int mod=1e9+7;

int f[N],rev[N],dp[NN][NN];

int tav(int n,int k){
	n%=mod; 
	if(k==0)return 1; 
	int ans=tav(n,k/2);
	ans*=ans; 
	ans%=mod;
	if(k%2==1)ans*=n; 
	ans%=mod; 
	return ans;
}
int choose(int n,int k){
	int ans=(f[n]*rev[k])%mod; 
	ans*=rev[n-k];
	ans%=mod; 
	return ans; 
}

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);	
	int n,k;
	cin>>n>>k;
	k--;
	if(k==0)return cout<<"1\n",0;
	f[0]=1;
	for(int i=1;i<N;i++)
		f[i]=(f[i-1]*i)%mod; 
	
	rev[N-1]=tav(f[N-1],mod-2);
	for(int i=N-2;i>=0;i--)
		rev[i]=(rev[i+1]*(i+1))%mod;
	
	dp[0][0]=1;
	for(int i=1,sum;i<n;i++){
		sum=dp[i-1][i-1];
		dp[i][i]=(sum*choose(i*k+k-1,k-1))%mod;
		for(int j=i-1;j>=0;j--){
			if(j!=0)sum+=dp[i-1][j-1];
			sum%=mod; 
			dp[i][j]=(sum*choose(i*k+i-j+k-1,k-1))%mod;
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		ans+=dp[n-1][i];
		ans%=mod;
	}
	cout<<(ans*f[n])%mod<<"\n";
	return 0;
}

Submission Info

Judge Result