Submission #2402455

---

Source Code Expand

#include <iostream>
using namespace std;

long long N, A, B, C, dp[5009][5009], fact[5009], factinv[5009], mod = 1000000007;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 30; i++) {
		if ((b / (1 << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}
long long Div(long long a, long long b, long long m) {
	return (a*modpow(b, m - 2, m)) % m;
}
void init() {
	fact[0] = 1; for (int i = 1; i <= 5000; i++) fact[i] = (fact[i - 1] * i) % mod;
	for (int i = 0; i <= 5000; i++) factinv[i] = Div(1, fact[i], mod);

	dp[0][0] = 1;
	for (int i = 1; i <= 5000; i++) {
		for (int j = 0; j <= 5000; j++) dp[i][j] += dp[i - 1][j];
		for (int j = 1; j <= 5000; j++) { dp[i][j] += dp[i][j - 1]; dp[i][j] %= mod; }
	}
}

int main() {
	init();
	cin >> N >> A >> B >> C;
	if (B % 2 == 1) { cout << "0" << endl; return 0; }
	long long sum = 0;
	for (int i = 0; i <= A; i++) {
		for (int j = 0; j <= C; j++) {
			long long a = i, b = (A - i), c = j, d = B / 2, n = (C - b - 3 * c);
			if (a < 0 || b < 0 || c < 0 || d < 0 || n < 0) continue;
			long long X = fact[a + b + c + d];
			X *= factinv[a]; X %= mod;
			X *= factinv[b]; X %= mod;
			X *= factinv[c]; X %= mod;
			X *= factinv[d]; X %= mod;
			X *= dp[d][n]; X %= mod;
			sum += X; sum %= mod;
		}
	}
	cout << sum << endl;
	return 0;
}

Submission Info

Judge Result