← 返回题目列表

Codeforces · 1931/G

G. 一维拼图

中文机器翻译题面 查看原题

你有一个一维拼图,其中的所有元素都需要排成一行,并相互连接。所有拼图元素都是完全白色的,只有形状不同才能相互区分。

每个元素在顶部和底部都有直边框,在左侧和右侧有连接,每个连接可以是突出或凹陷。您无法旋转元素。

您可以看到正好有 $$$4$$$ 类型的元素。如果左侧元素的右侧连接与右侧元素的左侧连接相反,则两个元素可以连接。

所有可能的元素类型。

拼图包含每种类型的 $$$c_1、c_2、c_3、c_4$$$ 元素。如果您成功地将所有元素组合成一条长链,则拼图被视为完成。您想知道有多少种方法可以做到这一点。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 输入测试用例的数量。测试用例的描述如下。

每个测试用例的描述包含 $$$4$$$ 整数 $$$c_i$$$ ($$$0 \le c_i \le 10^6$$$) — 分别是每种类型的元素数量。

保证所有测试用例的 $$$c_i$$$ 总和不超过 $$$4 \cdot 10^6$$$。

输出

对于每个测试用例,打印一个整数——解决难题的可能方法的数量。

如果存在$$$i$$$,则认为两个方法不同,使得这些方法中$$$i$$$位置的元素类型不同。

由于答案可能非常大,因此输出它对 $$$998244353$$$ 取模。

如果无法解决这个难题,请打印$$$0$$$。

示例

输入 #1

11
1 1 1 1
1 2 5 10
4 6 100 200
900000 900000 900000 900000
0 0 0 0
0 0 566 239
1 0 0 0
100 0 100 0
0 0 0 4
5 5 0 2
5 4 0 5

输出 #1

4
66
0
794100779
1
0
1
0
1
36
126