Submission #1084979

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint fact[5005], invf[5005];
lint dp[2505][5005];

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

lint bino(int x, int y){
	if(x < y) return 0;
	return fact[x] * (invf[y] * invf[x-y] % mod) % mod;
}

int n, a, b, c;

int main(){
	cin >> n >> a >> b >> c;
	if(b % 2 == 1){
		cout << 0 << endl;
		return 0;
	}
	b /= 2;
	fact[0] = invf[0] = 1;
	for(int i=1; i<=n; i++){
		fact[i] = fact[i-1] * i % mod;
		invf[i] = ipow(fact[i], mod - 2);
	}
	lint ret = 0;
	dp[0][0] = 1;
	for(int i=1; i<=b; i++){
		lint sum = 0;
		for(int j=0; j<=c; j++){
			sum += dp[i-1][j];
			sum %= mod;
			dp[i][j] = sum;
		}
	}
	for(int j=0; j<=c; j++){
		for(int k=0; k<=a; k++){
			if((c - j - k) >= 0 && (c - j - k) % 3 == 0){
				int cnt = (c - j - k) / 3;
				ret += dp[b][j] * ((bino(a, k) * bino(a + cnt + b, a + cnt) % mod) * bino(a + cnt, a) % mod);
				ret %= mod;
			}
		}
	}
	cout << ret << endl;
}

Submission Info

Judge Result