G. 一维拼图

每次测试时间限制：4 秒
内存限制：256 兆字节

你有一个一维拼图，所有拼图块需要排成一行，彼此连接。所有拼图块都是纯白色的，只有在形状不同的情况下才能区分彼此。

每个拼图块的顶部和底部是直边，左侧和右侧有连接结构，每个连接可以是凸起或凹槽。不能旋转拼图块。

可以看到，总共有恰好 4 种类型的拼图块。
两个拼图块可以连接，当且仅当左侧块的右侧连接与右侧块的左侧连接相反（即凸起对凹槽，凹槽对凸起）。

所有可能的拼图块类型如图所示。

拼图中包含 $c_1, c_2, c_3, c_4$ 个各类型的拼图块。如果能够将所有拼图块拼成一条长链，则认为拼图完成。你需要计算完成拼图的方法数。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 2 \cdot 10^5$），表示测试用例的数量。
接下来每个测试用例一行，包含四个整数 $c_i$（$0 \leq c_i \leq 10^6$），分别表示第 $1, 2, 3, 4$ 类拼图块的数量。

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

输出格式

对于每个测试用例，输出一个整数 —— 完成拼图的不同方法的数量，对 $998244353$ 取模。

如果无法完成拼图，输出 $0$。

两种方法不同，当存在某个位置 $i$ 使得两种排列中该位置上的拼图块类型不同。

示例

输入：

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