Submission #4090099

---

Source Code Expand

#ifndef ___CLASS_MODINT
#define ___CLASS_MODINT

#include <cstdint>

template<std::uint32_t mod>
class modint {
private:
	std::uint32_t n;
public:
	modint() : n(0) {};
	modint(std::uint64_t n_) : n(n_ % mod) {};
	bool operator==(const modint& m) const { return n == m.n; }
	bool operator!=(const modint& m) const { return n != m.n; }
	std::uint32_t get() const { return n; }
	modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; }
	modint operator+(const modint& m) const { return modint(*this) += m; }
	modint operator-(const modint& m) const { return modint(*this) -= m; }
	modint operator*(const modint& m) const { return modint(*this) *= m; }
	modint binpow(std::uint64_t b) const {
		modint ans = 1, m = modint(*this);
		while (b) {
			if (b & 1) ans *= m;
			m *= m;
			b >>= 1;
		}
		return ans;
	}
	modint inv() { return (*this).binpow(mod - 2); }
};

#endif // ___CLASS_MODINT

#include <vector>
#include <iostream>
#include <functional>
using namespace std;
const int mod = 1000000007;
using modulo = modint<mod>;
vector<modulo> convolve(vector<modulo> v1, vector<modulo> v2) {
	int s1 = v1.size(), s2 = v2.size();
	vector<modulo> ans(s1 + s2 - 1);
	for (int i = 0; i < s1; ++i) {
		for (int j = 0; j < s2; ++j) {
			ans[i + j] += v1[i] * v2[j];
		}
	}
	return ans;
}
modulo solve(int A, int B, int C) {
	if (B % 2 == 1) return 0;
	B /= 2;
	vector<modulo> fact(A + B + C + 1), inv(A + B + C + 1), factinv(A + B + C + 1);
	fact[0] = 1; inv[1] = 1; factinv[0] = 1;
	for (int i = 1; i <= A + B + C; ++i) fact[i] = fact[i - 1] * i;
	for (int i = 2; i <= A + B + C; ++i) inv[i] = inv[mod % i] * (mod - mod / i);
	for (int i = 1; i <= A + B + C; ++i) factinv[i] = factinv[i - 1] * inv[i];
	function<modulo(int, int)> comb = [&](int a, int b) {
		if (a < b || b < 0) return modulo(0);
		return fact[a] * factinv[b] * factinv[a - b];
	};
	vector<modulo> poly1(A + 1), poly2(C + 1);
	for (int i = 0; i <= A; ++i) poly1[i] = comb(A, i);
	for (int i = 0; i <= C; ++i) poly2[i] = comb(B + i - 1, B - 1);
	if (B == 0) poly2[0] = 1;
	vector<modulo> ans = convolve(poly1, poly2);
	modulo res = 0;
	for (int i = C; i >= 0; i -= 3) {
		modulo mul = fact[A + B + (C - i) / 3] * factinv[A] * factinv[B] * factinv[(C - i) / 3];
		res += mul * ans[i];
	}
	return res;
}
int main() {
	int A, B, C;
	cin >> A >> B >> C;
	modulo ans = solve(A, B, C);
	cout << ans.get() << endl;
	return 0;
}

Submission Info

Judge Result