← 返回题目列表

Codeforces · 2040/F

F. 立方体数量

中文机器翻译题面 查看原题

考虑一个长方体,其边为 $$$a$$$、$$$b$$$ 和 $$$c$$$,由 $$$k$$$ 不同颜色的单位立方体组成。我们可以在三个方向中的任何一个方向上对平行六面体应用循环移位任意次数$$$^{\text{*}}$$$。

有 $$$d_i$$$ 个颜色为 $$$i$$$ 的立方体 ($$$1 \le i \le k$$$)。这些立方体可以形成多少个不同的平行六面体(具有给定的边),其中任何两个都不能通过循环移位的某种组合而相等?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含四个整数:$$$a$$$、$$$b$$$、$$$c$$$ 和 $$$k$$$ ($$$1 \le a, b, c \le 3 \cdot 10^6$$$; $$$a \cdot b \cdot c \le 3 \cdot 10^6$$$; $$$1 \le k \le 10^6$$$) — 平行六面体的三边和单位立方体的颜色数量。

每个测试用例的第二行包含 $$$k$$$ 整数 $$$d_1, d_2, \ldots, d_k$$$ ($$$1 \le d_1 \le d_2 \le \ldots \le d_k \le 3 \cdot 10^6$$$) — 数组的元素 $$$d$$$: 立方体的数量给定颜色的。

保证在每个测试用例中,数组 $$$d$$$ 的元素总和等于 $$$a \cdot b \cdot c$$$。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$10 ^ 6$$$。

输出

对于每个测试用例,打印一个整数 - 不同平行六面体的数量以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

6
1 1 1 1
1
6 1 1 3
1 2 3
12 1 1 3
2 4 6
3 3 1 2
3 6
2 3 3 2
6 12
72 60 96 4
17280 86400 120960 190080

输出 #1

1
10
1160
12
1044
231490207

注意

在第一个测试用例中,只有一个平行六面体,它由一个单位立方体组成。

第二个测试用例中可能的平行六面体