C. Walk
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the following undirected graph, count the number of walks from $$$A$$$ to $$$A$$$ that visit nodes $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ exactly $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ times, respectively, modulo $$$998244353$$$.

Note: A walk from $$$A$$$ to $$$A$$$ is a sequence of vertices $$$v_0 = A,v_1,…,v_k = A$$$ such that for each $$$i$$$ $$$(0 \leq i \lt k)$$$, there is an edge between $$$v_i$$$ and $$$v_{i+1}$$$. Two walks are considered distinct if they are distinct as sequences.
Input

The first line contains $$$t$$$ $$$(1 \leq t \leq 100)$$$, the number of independent test cases. The description of the test cases follows.

The only line of each test case contains four integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ ($$$1 \leq a$$$, $$$b$$$, $$$c$$$, $$$d \leq 5 \cdot 10^5$$$).

The sum of $$$a$$$, the sum of $$$b$$$, the sum of $$$c$$$, and the sum of $$$d$$$ across all test cases does not exceed $$$5 \cdot 10^5$$$.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-20$$$ satisfy no additional constraints.

Output

For each test case, print the number of valid walks modulo $$$998244353$$$.

Example
Input
2
3 1 2 1
1 2 1 2
Output
6
0
Note

In the first test case, the $$$6$$$ walks are $$$ABDCACA$$$, $$$ACDBACA$$$, $$$ACDCABA$$$, $$$ABACDCA$$$, $$$ACABDCA$$$, and $$$ACACDBA$$$.

In the second test case, it can be shown that there are no valid walks.

—

Problem Idea: HaccerKat

Problem Preparation: HaccerKat

Occurrences: Novice J, Advanced C