计数 123

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

求满足以下所有条件的序列 $A=(a_1,\ldots,a_{X_1+X_2+X_3})$ 的数量，答案对 $998244353$ 取模。

• $A$ 中恰有 $X_1$ 个 $1$、$X_2$ 个 $2$ 和 $X_3$ 个 $3$。
• 对每个 $1\le i<X_1+X_2+X_3$，都有 $|a_{i+1}-a_i|\le 1$。

输入格式

输入一行三个整数 $X_1,X_2,X_3$。

输出格式

输出满足条件的序列数量对 $998244353$ 取模后的结果。

样例输入 1

2 2 1

样例输出 1

9

样例输入 2

5 3 4

样例输出 2

204

样例输入 3

998244 998353 998107

样例输出 3

701926019

样例解释 1

满足条件的序列共有 $9$ 个：

$(1,1,2,2,3)$、$(1,1,2,3,2)$、$(1,2,1,2,3)$、$(1,2,3,2,1)$、$(2,1,1,2,3)$、$(2,3,2,1,1)$、$(3,2,1,1,2)$、$(3,2,1,2,1)$、$(3,2,2,1,1)$。

数据范围

• $1\le X_1,X_2,X_3\le 10^6$；
• 输入均为整数。