你有一个一维拼图,其中的所有元素都需要排成一行,并相互连接。所有拼图元素都是完全白色的,只有形状不同才能相互区分。
每个元素在顶部和底部都有直边框,在左侧和右侧有连接,每个连接可以是突出或凹陷。您无法旋转元素。
您可以看到正好有 $$$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