记录编号	396361	评测结果	AAAAAAAAAAEEEEEEEEEE
题目名称	[HZOI 2015] Keller与驴蛋蛋与海蜇	最终得分	50
用户昵称	Go灬Fire	是否通过	未通过
代码语言	C++	运行时间	3.791 s
提交时间	2017-04-18 19:12:43	内存使用	99.55 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
#define fcl fclose(stdin);fclose(stdout);
const int maxn=13005000;
int mod,n,K;//K维空间，终点是(n,nnnnnn) 
int till,jc[maxn],inv[maxn];
struct Ques{
	int n,K;
}q[1050];
inline int qpow(int x,int h){
	int res=1;
	while(h){
		if(h&1) res=1ll*x*res%mod;
		x=1ll*x*x%mod;h>>=1; 
	}
	return res;
}
inline int C(int x,int y){
	return 1ll*jc[x]*inv[x-y]%mod*1ll*inv[y]%mod;
}
void Solve();
int main(){
	freopen("seaHibernate.in","r",stdin);freopen("seaHibernate.out","w",stdout);
	int T=0;scanf("%d%d",&mod,&T);
    register int i;
	for(i=1;i<=T;i++){
		scanf("%d%d",&q[i].K,&q[i].n);
		till=max(till,q[i].K*q[i].n);
	}
    jc[0]=1;
	for(i=1;i<=till;i++) jc[i]=1ll*jc[i-1]*i%mod;
	inv[0]=1;inv[till]=qpow(jc[n+n],mod-2);
	for(i=till-1;i;i--) inv[i]=1ll*(i+1)*inv[i+1]%mod;
	for(i=1;i<=T;i++){
		K=q[i].K;n=q[i].n;
		Solve();
	}
    getchar();getchar();
    return 0;
}
void Solve(){
	register int tot=1,ans=1,i;
	int sum=K*n;
	for(i=1;i<K;i++){
		tot=1ll*tot*C(sum,n)%mod;sum-=n;
		ans=1ll*ans*C(i+n,i)%mod;
	}
	printf("%d\n",1ll*tot*qpow(ans,mod-2)%mod);
}