您想要构造一个由小写拉丁字母组成的字符串 $$$s$$$,并且满足以下条件:
- 对于每对索引 $$$i$$$ 和 $$$j$$$,使得 $$$s_{i} = s_{j}$$$,这些索引的差是偶数,即 $$$|i - j| \bmod 2 = 0$$$。
构建任何字符串都太容易了,因此您将获得一个包含 $$$26$$$ 数字的数组 $$$c$$$ — 字符串 $$$s$$$ 中每个单独字母所需的出现次数。因此,对于 [1, 26]$$$ 中的每个 $$$i \in,拉丁字母表中的第 $$$i$$$ 字母应该恰好出现 $$$c_i$$$ 次。
你的任务是计算满足所有这些条件的不同字符串 $$$s$$$ 的数量。由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例包含 $$$26$$$ 整数 $$$c_{i}$$$ ($$$0 \le c_{i} \le 5 \cdot 10^{5}$$$) — 数组 $$$c$$$ 的元素。
输入数据的附加约束:
- 每个测试用例的 $$$c_{i}$$$ 之和为正;
- 所有测试用例的 $$$c_{i}$$$ 总和不超过 $$$5 \cdot 10^{5}$$$。
输出
对于每个测试用例,打印一个整数 - 合适字符串 $$$s$$$ 的数量,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
52 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 03 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 01 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 233527 233827
输出复制
4 960 0 1 789493841
注意
在第一个测试用例中,有 $$$4$$$ 合适的字符串:“阿巴克", "阿卡", "巴卡“和”卡巴".