#P18608. No Zero-Sum Subsegment

No Zero-Sum Subsegment

No Zero-Sum Subsegment

给定四个整数A、B、C、D,求满足以下要求的不同数组数量:数组中恰有A个-2、B个-1、C个1和D个2;任意非空连续子数组的元素之和都不为0。相同数值的元素不作区分。答案对998244353取模。

连续子数组是从原数组开头和末尾各删去若干元素后得到的一段连续元素。本题只禁止非空子数组的和为0。

输入格式

第一行一个整数T,表示测试用例数量。

接下来T行,每行四个整数A、B、C、D。

输出格式

每个测试用例输出一行一个整数,为所求数量对998244353取模的结果。

数据范围

1<=T<=100000,0<=A,B,C,D<=1000000,且A+B+C+D>0。不同测试用例之间没有总规模限制。

样例输入 1

5
69 0 0 0
1 1 1 1
0 0 3 3
6 1 0 6
10000 10000 1000000 1000000

样例输出 1

1
0
20
2
480402900

样例解释

第一组只有全部由69个-2组成的一种数组。第二组所有元素的总和为0,整个数组已经违反要求,因此答案为0。