Submission #1385771

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
typedef long long LL;
const LL mo=1e9+7;
LL fac[maxn],inv[maxn];
LL C(int n,int m){
	if(n<m)return 0;
	return fac[n]*inv[m]%mo*inv[n-m]%mo;
}
LL pw(LL x,LL k,LL p=::mo){
	LL ans=1;
	for(;k;k>>=1){
		if(k&1)ans=ans*x%mo;
		x=x*x%mo;
	}
	return ans;
}
int main(){
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<maxn;i++){
		fac[i]=fac[i-1]*i%mo;
	}
	for(int i=2;i<maxn;i++){
		inv[i]=(mo-mo/i)*inv[mo%i]%mo;
	}
	for(int i=2;i<maxn;i++){
		inv[i]=inv[i-1]*inv[i]%mo;
	}

	LL ans=0;


	int n,m,k;
	cin>>n>>m>>k;
	if(m>k)swap(m,k);


//	long long ans=0;
/*	for(int i=0;i<=m;i++)
		for(int j=0;j<=k;j++){
			ans+=C(n+i+j-1,n-1)*C(i+j,i)*pw(3,m+k-i-j);
		}
	cout<<ans<<endl;

	for(int i=0;i<=m+k;i++)
		for(int j=0;j<=k&&j<=m;j++){
			ans+=C(n+i-1,n-1)*C(i,j)*pw(3,m+k-i);
		}
	cout<<ansi<<endl;
	return 0;*/
	LL cur=1;
	for(int p=0;p<=m+k;p++){
		LL res=0;
		
		res=C(n+p-1,n-1)*pw(3,m+k-p)%mo;

		ans+=res*cur%mo;
		ans%=mo;

		cur=cur*2%mo;
		if(p>=m){
			cur-=C(p,m);
			cur+=mo;cur%=mo;
		}
		if(p>=k){
			cur-=C(p,p-k);
			cur+=mo;cur%=mo;
		}


	}

	cout<<ans<<endl;

	return 0;
}

Submission Info

Judge Result