311085: CF1931G. One-Dimensional Puzzle

G. One-Dimensional Puzzletime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have a one-dimensional puzzle, all the elements of which need to be put in one row, connecting with each other. All the puzzle elements are completely white and distinguishable from each other only if they have different shapes.

Each element has straight borders at the top and bottom, and on the left and right it has connections, each of which can be a protrusion or a recess. You cannot rotate the elements.

You can see that there are exactly $4$ types of elements. Two elements can be connected if the right connection of the left element is opposite to the left connection of the right element.

All possible types of elements.

The puzzle contains $c_1, c_2, c_3, c_4$ elements of each type. The puzzle is considered complete if you have managed to combine all elements into one long chain. You want to know how many ways this can be done.

Input

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^5$) — the number of input test cases. The descriptions of the test cases follow.

The description of each test case contains $4$ integers $c_i$ ($0 \le c_i \le 10^6$) — the number of elements of each type, respectively.

It is guaranteed that the sum of $c_i$ for all test cases does not exceed $4 \cdot 10^6$.

Output

For each test case, print one integer — the number of possible ways to solve the puzzle.

Two methods are considered different if there is $i$, such that the types of elements at the $i$ position in these methods differ.

Since the answer can be very large, output it modulo $998244353$.

If it is impossible to solve the puzzle, print $0$.

ExampleInput

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

Output

4
66
0
794100779
1
0
1
0
1
36
126

题目大意：
你有一个一维拼图，所有的元素需要被放置成一行，并且相互连接。所有的拼图元素都是纯白色的，只有形状不同才能区分。每个元素顶部和底部有直线边界，左右两侧有连接，每个连接可以是凸出的或凹陷的。你不能旋转元素。有4种类型的元素，两种元素可以通过一种方式连接：左边的元素的右连接与右边元素的左连接相反。拼图包含每种类型的c1, c2, c3, c4个元素。如果能够将所有元素组合成一个长链，则拼图完成。你需要计算完成拼图的方案数。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤2×10^5），表示输入测试用例的数量。
- 每个测试用例包含4个整数ci（0≤ci≤10^6），分别表示每种类型的元素的数量。

输出：
- 对于每个测试用例，输出一个整数，表示解决拼图的方案数。如果不可能解决拼图，则输出0。
- 由于答案可能非常大，请将结果模998244353后输出。

示例：
输入：
```
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
```
输出：
```
4
66
0
794100779
1
0
1
0
1
36
126
```题目大意： 你有一个一维拼图，所有的元素需要被放置成一行，并且相互连接。所有的拼图元素都是纯白色的，只有形状不同才能区分。每个元素顶部和底部有直线边界，左右两侧有连接，每个连接可以是凸出的或凹陷的。你不能旋转元素。有4种类型的元素，两种元素可以通过一种方式连接：左边的元素的右连接与右边元素的左连接相反。拼图包含每种类型的c1, c2, c3, c4个元素。如果能够将所有元素组合成一个长链，则拼图完成。你需要计算完成拼图的方案数。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤2×10^5），表示输入测试用例的数量。 - 每个测试用例包含4个整数ci（0≤ci≤10^6），分别表示每种类型的元素的数量。 输出： - 对于每个测试用例，输出一个整数，表示解决拼图的方案数。如果不可能解决拼图，则输出0。 - 由于答案可能非常大，请将结果模998244353后输出。 示例： 输入： ``` 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 ``` 输出： ``` 4 66 0 794100779 1 0 1 0 1 36 126 ```