前準備

\(n\) 個のものから順不同で \(k\) 個を選ぶ場合の数を \(\mathrm{binom}(n, k)\) としたとき，その値は

\[\mathrm{binom}(n, k) := \begin{cases} \frac{n!}{k!(n-k)!} & (n \geq k \geq 0) \\ 0 & (\mathrm{otherwise}) \end{cases}\]

です．

\(n\) 個並んだものを \(k\) 個の空でない列に分割する場合の数を \(\mathrm{part}(n, k)\) としたとき，その値は

\[\mathrm{part}(n, k) := \mathrm{binom}(n-1,\ k-1)\]

です．

考察

\(2\) 番目の条件は，「\(1\) と \(3\) が隣り合わない」と言い換えられます．

数列 \(A\) から \(1, 3\) のみを抽出した長さ \(X_1 + X_3\) の部分列 \(B\) を考えます．\(B\) の形は以下の \(4\) 通りあり，それぞれについての場合の数の総和を求めればよいです．

\(B\) の先頭も末尾も \(1\)

\(B\) 内で \(1\) が連続する極大な区間が \(i\) 個あるとします．

このとき，\(3\) が連続する極大な区間は \(i-1\) 個あります． このような \(B\) としてあり得るものは \(\mathrm{part}(X_1,\ i) \mathrm{part}(X_3,\ i-1)\) 通り存在します．

また，\(B\) 内で \(1,3\) が隣り合う箇所は \(2i-2\) 個あり，その間には必ず \(A\) において \(2\) が \(1\) 個以上挟まります．

よって，他の \(X_2 - (2i-2)\) 個の \(2\) を長さ \(X_1 + X_3\) の \(B\) の好きな位置に挿入したあとで，挟むべき \(2i-2\) 箇所に必要な \(2\) を挟むと考えれば，\(A\) 内の \(B\) の位置は \(\mathrm{binom}(X_1+X_2+X_3 - (i*2-2),\ X_1 + X_3)\) 通りあると分かります．

よって，\(\mathrm{part}(X_1,\ i) \mathrm{part}(X_3,\ i-1) \mathrm{binom}(X_1+X_2+X_3 - (i*2-2),\ X_1 + X_3)\) の値をすべての \(i\) で求め，それらの総和をとればよいです．

\(B\) の先頭も末尾も \(3\)

「\(B\) の先頭も末尾も \(1\)」の場合における \(X_1, X_3\) を交換した議論がそのまま成り立ちます．

\(B\) の先頭が \(1\)，末尾が \(3\)

\(B\) 内で \(1\) が連続する極大な区間が \(i\) 個あるとすると，\(3\) が連続する極大な区間は \(i\) 個，\(1,3\) が隣り合う箇所は \(2i-1\) 個あります．

よって，\(B\) としてあり得るものは \(\mathrm{part}(X_1,\ i) \mathrm{part}(X_3,\ i)\) 通り，\(A\) 内の \(B\) の位置は \( \mathrm{binom}(X_1+X_2+X_3 - (i*2-1),\ X_1 + X_3)\) 通りです．この積をすべての \(i\) で求め，それらの総和をとればよいです．

\(B\) の先頭が \(3\)，末尾が \(1\)

「\(B\) の先頭が \(1\)，末尾が \(3\)」の場合と同数です．

実装上の注意

\(N := X_1 + X_2 + X_3\) とおきます．

\(0 \leq k \leq N\) における \(k!\) およびその逆元の値を \(N + \log(MOD)\) 時間で前計算すれば，必要な二項係数の値は毎クエリ \(O(1)\) 時間で求まります．

実装例 (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
using std::pair;
using std::make_pair;
using std::min;
using std::max;
#include <algorithm>
using std::sort;
#include <deque>
using std::deque;
#include <cassert>

#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif

typedef long long int ll;
typedef pair<ll, ll> pr;

#include <atcoder/modint>
using mint = atcoder::modint998244353;

ll x1, x2, x3;

vector<mint> frac, invf;
void f_init (const ll n) {
	frac.resize(n+1);
	invf.resize(n+1);

	frac[0] = 1;
	for (ll i = 1; i <= n; i++) {
		frac[i] = frac[i-1] * i;
	}
	invf[n] = frac[n].inv();
	for (ll i = n; i >= 1; i--) {
		invf[i-1] = invf[i] * i;
	}
}
mint ncr (ll n, ll r) {
	if (n < 0 || n < r) return 0;
	return frac[n] * invf[r] * invf[n-r];
}
mint part1 (ll x, ll p) {
	return ncr(x-1, p-1);
}

void solve () {
	f_init(x1 + x2 + x3 + 10);

	mint ans = 0;

	// 13131...1
	for (ll i = 2; i <= x1; i++) {
		ans += part1(x1, i) * part1(x3, i-1) * ncr(x1+x2+x3 - (i*2-2), x1 + x3);
	}
	// 31313...3
	for (ll i = 2; i <= x3; i++) {
		ans += part1(x3, i) * part1(x1, i-1) * ncr(x1+x2+x3 - (i*2-2), x1 + x3);
	}
	// 1313...13, 3131...31
	for (ll i = 1; i <= min(x1, x3); i++) {
		ans += 2 * part1(x1, i) * part1(x3, i) * ncr(x1+x2+x3 - (i*2-1), x1 + x3);
	}

	cout << ans.val() << "\n";
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> x1 >> x2 >> x3;

	solve();
	

	return 0;
}