One-Dimensional Puzzle
Contest: Codeforces Round 925 (Div. 3)
Difficulty rating: 2000
Tags: combinatorics, math, number theory

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 format:
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 format:
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$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
4
66
0
794100779
1
0
1
0
1
36
126

Editorial:
Note that the elements of the $$$3$$$ and $$$4$$$ types on the right have a connection type opposite to that on the left. This means that what type of connection should be at the end of the chain to attach an element of any of these types will remain the same. Therefore, elements of these types can be combined into separate chains consisting only of elements of the same type. Joining such a chain will not change the type of connection at the end. Therefore, the basis of the chain consists of elements of the $$$1$$$ and $$$2$$$ types. First, you need to make the basis of a chain of only them, and then insert an arbitrary set of chains of elements of the $$$3$$$ and $$$4$$$ types.
In order to make the basis of the chain possible, it is necessary that $$$|c_1 - c_2| \le 1$$$ be executed. Otherwise, there will be extra elements left, and the answer is $$$0$$$. The basis of the chain can start with an element of type $$$i$$$ ($$$1\le i\le 2$$$) if $$$c_i\ge c_j$$$, where $$$j = 3 - i$$$ — an element of the opposite type ($$$1$$$ for $$$2$$$ and vice versa). If $$$c_1 = c_2$$$, then there are $$$2$$$ options for the basis of the chain, and they need to be counted separately.
To find the number of combinations at a fixed base of the chain, we calculate two values independently, and then multiply them:
• $$$x_1$$$ — the number of ways to arrange chains of $$$3$$$-type elements after $$$1$$$-type elements.
• $$$x_2$$$ — the number of ways to arrange chains of $$$4$$$-type elements after $$$2$$$-type elements.
$$$x_1$$$ and $$$x_2$$$ are calculated using the same formula, also known as the formula of balls and partitions. We want to arrange $$$m$$$ elements ($$$m$$$ is equal to $$$x_3$$$ or $$$x_4$$$, depending on which value we calculate). To arrange them, we have $$$n = n0 + add$$$ positions, where $$$n0$$$ is the number of elements of type $$$1$$$ or $$$2$$$ (similar to $$$m$$$), and $$$add$$$ is the value required to process an additional position equal to $$$1$$$ if the basis of the chain begins with an element of another type (then we can put the chain in front of it, for example, several elements of the $$$4$$$ type in front of the $$$1$$$ type element), and $$$0$$$ otherwise.
The number of ways to arrange $$$m$$$ indistinguishable elements in $$$n$$$ positions is $$$C_{n +m - 1}^{m}$$$, where $$$C_n^k$$$ is the number of combinations.
To calculate the answer, multiply the values of $$$x_1$$$ and $$$x_2$$$, and in the case when $$$c_1 = c_2$$$ — sum the resulting products.