#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; template auto range(T s, T e) { return views::iota(s, max(s, e)); } template auto range(T n) { return range(0, n); } template void take(vector& vec, int n) { vec.resize(n); for (int i = 0; i < n; ++i) cin >> vec[i]; } template void sout(const Args &...args) { ((cout << args << ' '), ...); } template void soutn(const Args &...args) { ((cout << args << ' '), ...); cout << '\n'; } template struct In2 { T1 a; T2 b; friend std::istream& operator>>(std::istream& is, In2& obj) { T1 t1; T2 t2; is >> t1 >> t2; obj = {t1, t2}; return is; } }; template struct In3 { T1 a; T2 b; T3 c; friend std::istream& operator>>(std::istream& is, In3& obj) { T1 t1; T2 t2; T3 t3; is >> t1 >> t2 >> t3; obj = {t1, t2, t3}; return is; } }; template struct In4 { T1 a; T2 b; T3 c; T4 d; friend std::istream& operator>>(std::istream& is, In4& obj) { T1 t1; T2 t2; T3 t3; T4 t4; is >> t1 >> t2 >> t3 >> t4; obj = {t1, t2, t3, t4}; return is; } }; #ifdef LOCAL #include #else #define dump(...) ; #endif const ll mod = 924844033; struct mint { ll x; mint(ll x_ = 0) : x((x_ % mod + mod) % mod) {} mint operator-() const { return mint(-x); } mint &operator+=(const mint &a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint &operator-=(const mint &a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; } mint &operator*=(const mint &a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint &a) const { mint res(*this); return res += a; } mint operator-(const mint &a) const { mint res(*this); return res -= a; } mint operator*(const mint &a) const { mint res(*this); return res *= a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t & 1) a *= *this; return a; } mint inv() const { return pow(mod - 2); } mint &operator/=(const mint &a) { return (*this) *= a.inv(); } mint operator/(const mint &a) const { mint res(*this); return res /= a; } auto operator<=>(const mint&) const = default; friend ostream &operator<<(ostream &os, const mint &m) { os << m.x; return os; } friend istream &operator>>(istream &is, mint &m) { is >> m.x; return is; } }; vector fact, invfact; void prepare(int n) { fact.resize(n + 1); invfact.resize(n + 1); fact[0] = 1; for (int i : range(n)) fact[i + 1] = fact[i] * (i + 1); invfact[n] = fact[n].inv(); for (int i = n; i >= 1; --i) invfact[i - 1] = invfact[i] * i; } mint combin(int n, int r) { if (r < 0 || r > n) return mint(0); return fact[n] * invfact[r] * invfact[n - r]; } using Poly = vector; Poly power(Poly a, ll b) { if (b == 0) return {1}; if (b % 2) return atcoder::convolution(a, power(a, b - 1)); else { Poly x = power(a, b / 2); return atcoder::convolution(x, x); } } template vector>>> make_vector4d(int x, int y, int z, int w, T init) { return vector>>>(x, vector>>(y, vector>(z, vector(w, init) ) ) ); } namespace { ll a, b, c; void read() { cin >> a >> b >> c; } mint naive() { auto dp = make_vector4d(a + 1, b + 1, c + 1, 6, mint(0)); dp[0][0][0][0] = 1; vector toa{1, 0, 3, 2, 5, 4}; vector tob{5, 3, 4, 1, 2, 0}; vector toc{2, 4, 0, 5, 1, 3}; for (int a0 : range(a + 1)) for (int b0 : range(b + 1)) for (int c0 : range(c + 1)) for (int v : range(6)) { if (a0 + b0 + c0 == 0) continue; if (a0 > 0) dp[a0][b0][c0][v] += dp[a0 - 1][b0][c0][toa[v]]; if (b0 > 0) dp[a0][b0][c0][v] += dp[a0][b0 - 1][c0][tob[v]]; if (c0 > 0) dp[a0][b0][c0][v] += dp[a0][b0][c0 - 1][toc[v]]; } dump("NAIVE", dp[a][b][c][0]); return dp[a][b][c][0]; } void naive_better() { auto dp = make_vector4d(a + 1, b + 1, c + 1, 1, mint(0)); dp[0][0][0][0] = mint(-1); for (int a0 : range(a + 1)) for (int b0 : range(b + 1)) for (int c0 : range(c + 1)) { if (a0 + b0 + c0 == 0) continue; if (a0 >= 2) dp[a0][b0][c0][0] += dp[a0 - 2][b0][c0][0]; if (b0 >= 2) dp[a0][b0][c0][0] += dp[a0][b0 - 2][c0][0]; if (c0 >= 2) dp[a0][b0][c0][0] += dp[a0][b0][c0 - 2][0]; if (a0 >= 1 && b0 >= 1) dp[a0][b0][c0][0] -= dp[a0 - 1][b0 - 1][c0][0]; if (b0 >= 1 && c0 >= 1) dp[a0][b0][c0][0] -= dp[a0][b0 - 1][c0 - 1][0]; if (c0 >= 1 && a0 >= 1) dp[a0][b0][c0][0] -= dp[a0 - 1][b0][c0 - 1][0]; } mint base = fact[a + b + c] * invfact[a] * invfact[b] * invfact[c]; mint s = dp[a][b][c][0]; mint t = (base - s * 2) / 3; dump("NAIVE BETTER S", s); dump("NAIVE BETTER ans", t); } void naive_better_rot() { auto dp = vector>(a + 3, vector(b + 3)); dp[0][0] = -1; for (int it : range((a + b + c) / 2)) { auto next = vector>(a + 3, vector(b + 3)); for (int a0 : range(a + 1)) for (int b0 : range(b + 1)) { next[a0 + 0][b0 + 0] += dp[a0][b0]; next[a0 + 1][b0 + 0] -= dp[a0][b0]; next[a0 + 1][b0 + 1] -= dp[a0][b0]; next[a0 + 0][b0 + 1] -= dp[a0][b0]; next[a0 + 0][b0 + 2] += dp[a0][b0]; next[a0 + 2][b0 + 0] += dp[a0][b0]; } dp.swap(next); } dump("NAIVE BETTER ROT S=", dp[a][b]); } mint sign(int m) { return m % 2 ? -1 : 1; } mint run() { if ((a + b + c) % 2) return 0; ll n = (a + b + c) / 2; prepare(2 * n + 10); Poly T{1, mod - 1, 1}; Poly Tn = power(T, n); mint res; for (ll k : range(2 * n + 1)) { dump("===="); dump(k); dump(Tn[k]); dump(combin(k, a) * sign(k - a)); dump(combin(2 * n - k, b) * sign(2 * n - k - b)); res += mint(Tn[k]) * combin(k, a) * sign(k - a) * combin(2 * n - k, b) * sign(2 * n - k - b); } res = -res; dump("FINAL S", res); mint base = fact[a + b + c] * invfact[a] * invfact[b] * invfact[c]; res = (base - res * 2) / 3; dump("FINAL ans", res); return res; } void nop() { naive(); naive_better(); naive_better_rot(); } } // namespace template void exec(F f) { if constexpr (std::is_same_v) f(); else cout << f() << endl; } int main(int argc, char** argv) { cerr << fixed << setprecision(12); cout << fixed << setprecision(12); int testcase = 1; if (argc > 1) testcase = atoi(argv[1]); while (testcase--) { read(); } exec(run); }