#include // created [2019/12/02] 23:55:48 #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wsign-conversion" using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; using uint = unsigned int; using usize = std::size_t; using ll = long long; using ull = unsigned long long; using ld = long double; template constexpr T popcount(const T u) { return u ? static_cast(__builtin_popcountll(static_cast(u))) : static_cast(0); } template constexpr T log2p1(const T u) { return u ? static_cast(64 - __builtin_clzll(static_cast(u))) : static_cast(0); } template constexpr T msbp1(const T u) { return log2p1(u); } template constexpr T lsbp1(const T u) { return __builtin_ffsll(u); } template constexpr T clog(const T u) { return u ? log2p1(u - 1) : static_cast(u); } template constexpr bool ispow2(const T u) { return u and (static_cast(u) & static_cast(u - 1)) == 0; } template constexpr T ceil2(const T u) { return static_cast(1) << clog(u); } template constexpr T floor2(const T u) { return u == 0 ? static_cast(0) : static_cast(1) << (log2p1(u) - 1); } template constexpr bool btest(const T mask, const usize ind) { return static_cast((static_cast(mask) >> ind) & static_cast(1)); } template void bset(T& mask, const usize ind) { mask |= (static_cast(1) << ind); } template void breset(T& mask, const usize ind) { mask &= ~(static_cast(1) << ind); } template void bflip(T& mask, const usize ind) { mask ^= (static_cast(1) << ind); } template void bset(T& mask, const usize ind, const bool b) { (b ? bset(mask, ind) : breset(mask, ind)); } template constexpr T bcut(const T mask, const usize ind) { return ind == 0 ? static_cast(0) : static_cast((static_cast(mask) << (64 - ind)) >> (64 - ind)); } template bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); } template bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); } constexpr unsigned int mod = 1000000007; template constexpr T inf_v = std::numeric_limits::max() / 4; template constexpr Real pi_v = Real{3.141592653589793238462643383279502884}; template T read() { T v; return std::cin >> v, v; } template auto read(const usize size, Args... args) { std::vector(args...))> ans(size); for (usize i = 0; i < size; i++) { ans[i] = read(args...); } return ans; } template auto reads() { return std::tuple...>{read()...}; } # define SHOW(...) static_cast(0) template std::vector make_v(const usize size, const T v) { return std::vector(size, v); } template auto make_v(const usize size, Args... args) { return std::vector(size, make_v(args...)); } template T gcd(const T& a, const T& b) { return a < 0 ? gcd(-a, b) : b < 0 ? gcd(a, -b) : (a > b ? gcd(b, a) : a == 0 ? b : gcd(b % a, a)); } template T lcm(const T& a, const T& b) { return a / gcd(a, b) * b; } template constexpr std::pair extgcd(const T a, const T b) { if (b == 0) { return std::pair{1, 0}; } const auto g = gcd(a, b), da = std::abs(b) / g; const auto p = extgcd(b, a % b); const auto x = (da + p.second % da) % da, y = (g - a * x) / b; return {x, y}; } template constexpr T inverse(const T a, const T mod) { return extgcd(a, mod).first; } template class modint_base { public: template static std::enable_if_t mod() { return mod_ref(); } template static constexpr std::enable_if_t mod() { return mod_value; } template static void set_mod(const std::enable_if_t mod) { mod_ref() = mod, inv_ref() = {1, 1}; } modint_base() : v{0} {} modint_base(const ll val) : v{norm(static_cast(val % static_cast(mod()) + static_cast(mod())))} {} modint_base(const modint_base& n) : v{n()} {} explicit operator bool() const { return v != 0; } bool operator!() const { return not static_cast(*this); } modint_base& operator=(const modint_base& m) { return v = m(), (*this); } modint_base& operator=(const ll val) { return v = norm(uint(val % static_cast(mod()) + static_cast(mod()))), (*this); } friend modint_base operator+(const modint_base& m) { return m; } friend modint_base operator-(const modint_base& m) { return make(norm(mod() - m.v)); } friend modint_base operator+(const modint_base& m1, const modint_base& m2) { return make(norm(m1.v + m2.v)); } friend modint_base operator-(const modint_base& m1, const modint_base& m2) { return make(norm(m1.v + mod() - m2.v)); } friend modint_base operator*(const modint_base& m1, const modint_base& m2) { return make(static_cast(static_cast(m1.v) * static_cast(m2.v) % static_cast(mod()))); } friend modint_base operator/(const modint_base& m1, const modint_base& m2) { return m1 * inv(m2.v); } friend modint_base operator+(const modint_base& m, const ll val) { return modint_base{static_cast(m.v) + val}; } friend modint_base operator-(const modint_base& m, const ll val) { return modint_base{static_cast(m.v) - val}; } friend modint_base operator*(const modint_base& m, const ll val) { return modint_base{static_cast(m.v) * (val % static_cast(mod()))}; } friend modint_base operator/(const modint_base& m, const ll val) { return modint_base{static_cast(m.v) * inv(val)}; } friend modint_base operator+(const ll val, const modint_base& m) { return modint_base{static_cast(m.v) + val}; } friend modint_base operator-(const ll val, const modint_base& m) { return modint_base{-static_cast(m.v) + val}; } friend modint_base operator*(const ll val, const modint_base& m) { return modint_base{static_cast(m.v) * (val % static_cast(mod()))}; } friend modint_base operator/(const ll val, const modint_base& m) { return modint_base{val * inv(static_cast(m.v))}; } friend modint_base& operator+=(modint_base& m1, const modint_base& m2) { return m1 = m1 + m2; } friend modint_base& operator-=(modint_base& m1, const modint_base& m2) { return m1 = m1 - m2; } friend modint_base& operator*=(modint_base& m1, const modint_base& m2) { return m1 = m1 * m2; } friend modint_base& operator/=(modint_base& m1, const modint_base& m2) { return m1 = m1 / m2; } friend modint_base& operator+=(modint_base& m, const ll val) { return m = m + val; } friend modint_base& operator-=(modint_base& m, const ll val) { return m = m - val; } friend modint_base& operator*=(modint_base& m, const ll val) { return m = m * val; } friend modint_base& operator/=(modint_base& m, const ll val) { return m = m / val; } friend modint_base operator^(const modint_base& m, const ll n) { return power(m.v, n); } friend modint_base& operator^=(modint_base& m, const ll n) { return m = m ^ n; } friend bool operator==(const modint_base& m1, const modint_base& m2) { return m1.v == m2.v; } friend bool operator!=(const modint_base& m1, const modint_base& m2) { return not(m1 == m2); } friend bool operator==(const modint_base& m, const ll val) { return m.v == norm(static_cast(static_cast(mod()) + val % static_cast(mod()))); } friend bool operator!=(const modint_base& m, const ll val) { return not(m == val); } friend bool operator==(const ll val, const modint_base& m) { return m.v == norm(static_cast(static_cast(mod()) + val % static_cast(mod()))); } friend bool operator!=(const ll val, const modint_base& m) { return not(m == val); } friend std::istream& operator>>(std::istream& is, modint_base& m) { ll v; return is >> v, m = v, is; } friend std::ostream& operator<<(std::ostream& os, const modint_base& m) { return os << m(); } uint operator()() const { return v; } static modint_base small_inv(const usize n) { auto& in = inv_ref(); if (n < in.size()) { return in[n]; } for (usize i = in.size(); i <= n; i++) { in.push_back(-in[modint_base::mod() % i] * (modint_base::mod() / i)); } return in.back(); } private: template static std::enable_if_t mod_ref() { static UInt mod = 0; return mod; } static uint norm(const uint x) { return x < mod() ? x : x - mod(); } static modint_base make(const uint x) { modint_base m; return m.v = x, m; } static modint_base power(modint_base x, ull n) { modint_base ans = 1; for (; n; n >>= 1, x *= x) { if (n & 1) { ans *= x; } } return ans; } static modint_base inv(const ll v) { return v < 1000000 ? small_inv(static_cast(v)) : modint_base{inverse(v, static_cast(mod()))}; } static std::vector& inv_ref() { static std::vector in{1, 1}; return in; } uint v; }; template using modint = modint_base; template using dynamic_modint = modint_base; template class modcomb_base { public: using value_type = modint_base; modcomb_base() = delete; static void set_mod(const uint mod) { value_type::set_mod(mod), fact_ref() = {1, 1}, inv_fact_ref() = {1, 1}; } static value_type fact(const usize n) { auto& f = fact_ref(); if (n < f.size()) { return f[n]; } for (usize i = f.size(); i <= n; i++) { f.push_back(f.back() * i); } return f.back(); } static value_type inv_fact(const usize n) { auto& invf = inv_fact_ref(); if (n < invf.size()) { return invf[n]; } for (usize i = invf.size(); i <= n; i++) { invf.push_back(invf.back() * value_type::small_inv(i)); } return invf.back(); } static value_type perm(const usize n, const usize k) { return k > n ? value_type{0} : fact(n) * inv_fact(n - k); } static value_type comb(const usize n, const usize k) { return k > n ? value_type{0} : fact(n) * inv_fact(n - k) * inv_fact(k); } private: static std::vector& fact_ref() { static std::vector f{1, 1}; return f; } static std::vector& inv_fact_ref() { static std::vector invf{1, 1}; return invf; } }; template using modcomb = modcomb_base; template using dynamic_modcomb = modcomb_base; template struct complex { using value_type = Real; complex() : real{Real{0}}, imag{Real{0}} {} complex(const complex&) = default; complex(const Real& theta) : real(std::cos(theta)), imag(std::sin(theta)) {} complex(const Real& r, const Real& i) : real{r}, imag{i} {} ~complex() = default; friend complex operator+(const complex& c) { return c; } friend complex operator-(const complex& c) { return complex{-c.real, -c.imag}; } friend complex operator+(const complex& c1, const complex& c2) { return complex{c1.real + c2.real, c1.imag + c2.imag}; } friend complex operator-(const complex& c1, const complex& c2) { return complex{c1.real - c2.real, c1.imag - c2.imag}; } friend complex operator*(const complex& c1, const complex& c2) { return complex{c1.real * c2.real - c1.imag * c2.imag, c1.real * c2.imag + c1.imag * c2.real}; } friend complex operator*(const complex& c, const Real& r) { return complex{c.real * r, c.imag * r}; } friend complex operator/(complex& c1, complex& c2) { c1* c2.conj() / c2.norm(); } friend bool operator==(const complex& c1, const complex& c2) { return c1.real == c2.real and c1.imag == c2.imag; } friend bool operator!=(const complex& c1, const complex& c2) { return not(c1 == c2); } friend complex& operator+=(complex& c1, const complex& c2) { return c1.real += c2.real, c1.imag += c2.imag, c1; } friend complex& operator-=(complex& c1, const complex& c2) { return c1.real += c2.real, c1.imag += c2.imag, c1; } friend complex& operator*=(complex& c1, const complex& c2) { return c1 = c1 * c2; } friend complex& operator*=(complex& c, const Real& r) { return c = c * r; } friend complex& operator/=(complex& c1, const complex& c2) { return c1 = c1 / c2; } complex conj() const { return complex{real, -imag}; } Real norm() const { return real * real + imag * imag; } Real abs() const { return std::sqrt(norm()); } Real arg() const { return std::atan2(imag, real); } friend std::ostream& operator<<(std::ostream& os, const complex& c) { return os << c.real << "+" << c.imag << "i"; } Real real, imag; }; template class fft { private: static constexpr usize depth = 30; static constexpr Real pi = pi_v; static void transform(std::vector>& a, const usize lg, const bool rev) { static std::vector> root[depth]; const usize sz = a.size(); assert((1UL << lg) == sz); if (root[lg].empty()) { root[lg].reserve(sz), root[lg].resize(sz); for (usize i = 0; i < sz; i++) { root[lg][i] = complex(pi * Real(2 * i) / Real(sz)); } } std::vector> tmp(sz); for (usize w = (sz >> 1); w > 0; w >>= 1) { for (usize y = 0; y < (sz >> 1); y += w) { const complex r = rev ? root[lg][y].conj() : root[lg][y]; for (usize x = 0; x < w; x++) { const auto u = a[y << 1 | x], v = a[y << 1 | x | w] * r; tmp[y | x] = u + v, tmp[y | x | (sz >> 1)] = u - v; } } std::swap(tmp, a); } } public: using value_type = Real; fft() = delete; template static std::vector simple_convolute(const std::vector& a, const std::vector& b) { const usize need = a.size() + b.size() - 1, lg = clog(need), sz = 1UL << lg; std::vector> x(sz), y(sz); for (usize i = 0; i < a.size(); i++) { x[i] = {(Real)a[i], (Real)0}; } for (usize i = 0; i < b.size(); i++) { y[i] = {(Real)b[i], (Real)0}; } transform(x, lg, false), transform(y, lg, false); for (usize i = 0; i < sz; i++) { x[i] *= y[i]; } transform(x, lg, true); std::vector ans(need); for (usize i = 0; i < need; i++) { ans[i] = (T)std::round(x[i].real / (Real)sz); } return ans; } template static std::vector convolute(const std::vector& a, const std::vector& b) { constexpr usize bitnum = (depth + division - 1) / division; const usize need = a.size() + b.size() - 1, lg = clog(need), sz = 1UL << lg; std::vector> x[division], y[division], tmp(sz); for (usize i = 0; i < division; i++) { x[i].reserve(sz), x[i].resize(sz), y[i].reserve(sz), y[i].resize(sz); std::fill(tmp.begin() + std::min(a.size(), b.size()), tmp.end(), complex{}); for (usize j = 0; j < a.size(); j++) { tmp[j].real = value_type((a[j] >> (bitnum * i)) & ((1 << bitnum) - 1)); } for (usize j = 0; j < b.size(); j++) { tmp[j].imag = value_type((b[j] >> (bitnum * i)) & ((1 << bitnum) - 1)); } transform(tmp, lg, false); for (usize j = 0; j < sz; j++) { tmp[j] *= value_type(0.5); } for (usize j = 0; j < sz; j++) { const usize k = j == 0 ? 0UL : sz - j; x[i][j] = complex{tmp[j].real + tmp[k].real, tmp[j].imag - tmp[k].imag}, y[i][j] = complex{tmp[j].imag + tmp[k].imag, -tmp[j].real + tmp[k].real}; } } std::vector> z[division]; for (usize i = 0; i < division; i++) { z[i].reserve(sz), z[i].resize(sz); } for (usize a = 0; a < division; a++) { for (usize b = 0; b < division; b++) { for (usize i = 0; i < sz; i++) { if (a + b < division) { z[a + b][i] += x[a][i] * y[b][i]; } else { z[a + b - division][i] += x[a][i] * y[b][i] * complex(0, 1); } } } } for (usize i = 0; i < division; i++) { transform(z[i], lg, true); } std::vector ans(need); T base = 1; for (usize k = 0; k < 2 * division - 1; k++, base *= (1LL << bitnum)) { for (usize i = 0; i < need; i++) { if (k < division) { ans[i] += base * T(std::round(z[k][i].real / value_type(sz))); } else { ans[i] += base * T(std::round(z[k - division][i].imag / value_type(sz))); } } } return ans; } template static std::vector> convolute(const std::vector>& a, const std::vector>& b) { using mint = modint_base; constexpr usize bitnum = (depth + division - 1) / division; const usize need = a.size() + b.size() - 1, lg = clog(need), sz = 1UL << lg; std::vector> x[division], y[division], tmp(sz); for (usize i = 0; i < division; i++) { x[i].reserve(sz), x[i].resize(sz), y[i].reserve(sz), y[i].resize(sz); std::fill(tmp.begin() + std::min(a.size(), b.size()), tmp.end(), complex{}); for (usize j = 0; j < a.size(); j++) { tmp[j].real = value_type((a[j]() >> (bitnum * i)) & ((1 << bitnum) - 1)); } for (usize j = 0; j < b.size(); j++) { tmp[j].imag = value_type((b[j]() >> (bitnum * i)) & ((1 << bitnum) - 1)); } transform(tmp, lg, false); for (usize j = 0; j < sz; j++) { tmp[j] *= value_type(0.5); } for (usize j = 0; j < sz; j++) { const usize k = j == 0 ? 0UL : sz - j; x[i][j] = complex{tmp[j].real + tmp[k].real, tmp[j].imag - tmp[k].imag}, y[i][j] = complex{tmp[j].imag + tmp[k].imag, -tmp[j].real + tmp[k].real}; } } std::vector> z[division]; for (usize i = 0; i < division; i++) { z[i].reserve(sz), z[i].resize(sz); } for (usize a = 0; a < division; a++) { for (usize b = 0; b < division; b++) { for (usize i = 0; i < sz; i++) { if (a + b < division) { z[a + b][i] += x[a][i] * y[b][i]; } else { z[a + b - division][i] += x[a][i] * y[b][i] * complex(0, 1); } } } } for (usize i = 0; i < division; i++) { transform(z[i], lg, true); } std::vector ans(need); mint base = 1; for (usize k = 0; k < 2 * division - 1; k++, base *= (1LL << bitnum)) { for (usize i = 0; i < need; i++) { if (k < division) { ans[i] += int((base * ll(std::round(z[k][i].real / value_type(sz))))()); } else { ans[i] += int((base * ll(std::round(z[k - division][i].imag / value_type(sz))))()); } } } return ans; } }; int main() { using mint = modint; using moc = modcomb; const auto [X, Y, Z] = reads(); const int T = X + Y + Z; if (T == 0) { return std::cout << 1 << std::endl, 0; } std::vector sum(T + 1, 0); for (int i = 1; i <= T; i++) { sum[i] = moc::comb(X + i - 1, X) * moc::comb(Y + i - 1, Y) * moc::comb(Z + i - 1, Z); sum[i] *= moc::inv_fact(i); } std::vector diff(T + 1, 0); for (int i = 0; i <= T; i++) { diff[i] = moc::inv_fact(i) * (i % 2 == 0 ? 1 : -1); } auto res = fft<>::convolute(sum, diff); mint ans = 0; for (int i = 0; i <= T; i++) { ans += res[i] * moc::fact(i); } std::cout << ans << std::endl; return 0; }