建议数据提升到 1e12(a,b,c,d<=1e12 k<=1e6)

这样就只能用 lucas+组合数学

而 DP 的逃课算法就不能过

tips：为什么是 1e12

A ：我们学校教练过于善良（逆天），

数据提升到了1e12；

（由于数据下不下来，暂时不给出）

但是一点肯定：

in.1:

123123123123
321321321321
232323
212121321123
32134

out.1:

88487

顺便给个我自己的代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL jc[100010],ni[100010],mod=1e5+3;
LL ksm(LL x,LL y){
	LL ret=x,ans=1;
	while(y){
		if(y&1)ans=ans*ret%mod;
		y=y>>1;
		ret=ret*ret%mod;
	}
	return ans;
}
void asd(){
	jc[1]=jc[0]=1;ni[1]=ni[0]=1;
	for(int i=2;i<mod;i++)jc[i]=jc[i-1]*i%mod;
	for(int i=2;i<mod;i++)ni[i]=ksm(jc[i],mod-2);
	return ;
}
LL C(LL n,LL m){
	if(m>n)return 0;
	return jc[n]*ni[m]*ni[n-m]%mod;
}
LL lucas(LL n,LL m){
	if(n<mod&&m<mod)return C(n,m);
	return lucas(n/mod,m/mod)*lucas(n%mod,m%mod);
}
LL f(LL n,LL m,LL k){
	return lucas(n,k)*lucas(m,k)*jc[k%mod]%mod;
}
int main (){
	asd();LL a,b,c,d,k;
	scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
	LL ans=0;
	for(int i=0;i<=k;i++){
		ans+=f(a,b,i)*f(a+c-i,d,k-i);
		ans%=mod;
	}
	cout<<ans;
	return 0;
}

请各位 民间/管理员 大神 帮忙验证：

争取让他早日升紫！