#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } // a^-1 (mod m) // m > 0 Int modInv(Int a, Int m) { Int b = m, x = 1, y = 0, t; for (; ; ) { t = a / b; a -= t * b; if (a == 0) { assert(b == 1 || b == -1); if (b == -1) y = -y; return (y < 0) ? (y + m) : y; } x -= t * y; t = b / a; b -= t * a; if (b == 0) { assert(a == 1 || a == -1); if (a == -1) x = -x; return (x < 0) ? (x + m) : x; } y -= t * x; } } // M: prime, G: primitive root template struct Fft { // 1, 1/4, 1/8, 3/8, 1/16, 5/16, 3/16, 7/16, ... int g[1 << (K - 1)]; constexpr Fft() : g() { static_assert(K >= 2, "Fft: K >= 2 must hold"); static_assert(!((M - 1) & ((1 << K) - 1)), "Fft: 2^K | M - 1 must hold"); g[0] = 1; long long g2 = G, gg = 1; for (int e = (M - 1) >> K; e; e >>= 1) { if (e & 1) gg = (gg * g2) % M; g2 = (g2 * g2) % M; } g[1 << (K - 2)] = gg; for (int l = 1 << (K - 2); l >= 2; l >>= 1) { g[l >> 1] = (static_cast(g[l]) * g[l]) % M; } assert((static_cast(g[1]) * g[1]) % M == M - 1); for (int l = 2; l <= 1 << (K - 2); l <<= 1) { for (int i = 1; i < l; ++i) { g[l + i] = (static_cast(g[l]) * g[i]) % M; } } } void fft(vector &x) const { const int n = x.size(); assert(!(n & (n - 1)) && n <= 1 << K); for (int l = n; l >>= 1; ) { for (int i = 0; i < (n >> 1) / l; ++i) { for (int j = (i << 1) * l; j < (i << 1 | 1) * l; ++j) { const int t = (static_cast(g[i]) * x[j + l]) % M; if ((x[j + l] = x[j] - t) < 0) x[j + l] += M; if ((x[j] += t) >= M) x[j] -= M; } } } for (int i = 0, j = 0; i < n; ++i) { if (i < j) std::swap(x[i], x[j]); for (int l = n; (l >>= 1) && !((j ^= l) & l); ) {} } } vector convolution(const vector &a, const vector &b) const { const int na = a.size(), nb = b.size(); int n, invN = 1; for (n = 1; n < na + nb - 1; n <<= 1) invN = ((invN & 1) ? (invN + M) : invN) >> 1; vector x(n, 0), y(n, 0); std::copy(a.begin(), a.end(), x.begin()); std::copy(b.begin(), b.end(), y.begin()); fft(x); fft(y); for (int i = 0; i < n; ++i) x[i] = (((static_cast(x[i]) * y[i]) % M) * invN) % M; std::reverse(x.begin() + 1, x.end()); fft(x); x.resize(na + nb - 1); return x; } }; template struct ModInt { static constexpr int M = M_; int x; constexpr ModInt() : x(0) {} constexpr ModInt(long long x_) : x(x_ % M) { if (x < 0) x += M; } ModInt &operator+=(const ModInt &a) { x += a.x; if (x >= M) x -= M; return *this; } ModInt &operator-=(const ModInt &a) { x -= a.x; if (x < 0) x += M; return *this; } ModInt &operator*=(const ModInt &a) { x = static_cast((static_cast(x) * a.x) % M); return *this; } ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); } ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); } ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); } ModInt operator-() const { return ModInt(-x); } ModInt pow(long long e) const { ModInt x2 = x, xe = 1; for (; e; e >>= 1) { if (e & 1) xe *= x2; x2 *= x2; } return xe; } ModInt inv() const { int a = x, b = M, y = 1, z = 0, t; for (; ; ) { t = a / b; a -= t * b; if (a == 0) { assert(b == 1 || b == -1); return ModInt(b * z); } y -= t * z; t = b / a; b -= t * a; if (b == 0) { assert(a == 1 || a == -1); return ModInt(a * y); } z -= t * y; } } friend ModInt operator+(long long a, const ModInt &b) { return (ModInt(a) += b); } friend ModInt operator-(long long a, const ModInt &b) { return (ModInt(a) -= b); } friend ModInt operator*(long long a, const ModInt &b) { return (ModInt(a) *= b); } friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; } }; constexpr Int MO = 1'000'000'007; using Mint = ModInt; constexpr int LIM = 3'000'000; Mint inv[LIM], fac[LIM], invFac[LIM]; void prepare() { inv[1] = 1; for (int i = 2; i < LIM; ++i) { inv[i] = -(Mint::M / i) * inv[Mint::M % i]; } fac[0] = invFac[0] = 1; for (int i = 1; i < LIM; ++i) { fac[i] = fac[i - 1] * i; invFac[i] = invFac[i - 1] * inv[i]; } } Mint binom(Int n, Int k) { if (0 <= k && k <= n) { assert(n < LIM); return fac[n] * invFac[k] * invFac[n - k]; } else { return 0; } } constexpr Int FFT_P0 = 469762049; // 2^26 7 + 1 constexpr Int FFT_P1 = 167772161; // 2^25 5 + 1 constexpr Int FFT_P2 = 754974721; // 2^24 45 + 1 const Fft FFT0; const Fft FFT1; const Fft FFT2; vector multiply(const vector &a, const vector &b) { const Int FFT_INV01 = modInv(FFT_P0, FFT_P1); const Int FFT_INV012 = modInv(FFT_P0 * FFT_P1, FFT_P2); vector aa(a.size()), bb(b.size()); for (size_t i = 0; i < a.size(); ++i) aa[i] = a[i].x % FFT_P0; for (size_t i = 0; i < b.size(); ++i) bb[i] = b[i].x % FFT_P0; const vector x0 = FFT0.convolution(aa, bb); for (size_t i = 0; i < a.size(); ++i) aa[i] = a[i].x % FFT_P1; for (size_t i = 0; i < b.size(); ++i) bb[i] = b[i].x % FFT_P1; const vector x1 = FFT1.convolution(aa, bb); for (size_t i = 0; i < a.size(); ++i) aa[i] = a[i].x % FFT_P2; for (size_t i = 0; i < b.size(); ++i) bb[i] = b[i].x % FFT_P2; const vector x2 = FFT2.convolution(aa, bb); if(a.size()<=10){ cerr<<"x0 = ";pv(x0.begin(),x0.end()); cerr<<"x1 = ";pv(x1.begin(),x1.end()); cerr<<"x2 = ";pv(x2.begin(),x2.end()); } vector x(x0.size()); for (size_t i = 0; i < x0.size(); ++i) { Int y0 = x0[i] % FFT_P0; Int y1 = (FFT_INV01 * (x1[i] - y0)) % FFT_P1; if (y1 < 0) { y1 += FFT_P1; } Int y2 = (FFT_INV012 * ((x2[i] - y0 - FFT_P0 * y1) % FFT_P2)) % FFT_P2; if (y2 < 0) { y2 += FFT_P2; } x[i] = Mint(1) * y0 + Mint(FFT_P0) * y1 + Mint(FFT_P0 * FFT_P1) * y2; } return x; } int main() { prepare(); int X, Y, Z; for (; ~scanf("%d%d%d", &X, &Y, &Z); ) { const int n = X + Y + Z; vector a(n + 1), b(n + 1); for (int i = 0; i <= n; ++i) { a[i] = invFac[i] * binom(X + i - 1, i - 1) * binom(Y + i - 1, i - 1) * binom(Z + i - 1, i - 1); b[i] = ((i % 2 != 0) ? -1 : +1) * invFac[i]; } if(n<=10){ cerr<<"a = ";pv(a.begin(),a.end()); cerr<<"b = ";pv(b.begin(),b.end()); } const vector res = multiply(a, b); Mint ans = 0; for (int i = 0; i <= n; ++i) { ans += fac[i] * res[i]; } printf("%d\n", ans.x); } return 0; }