F. Number of Cubestime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputConsider a rectangular parallelepiped with sides $$$a$$$, $$$b$$$, and $$$c$$$, that consists of unit cubes of $$$k$$$ different colors. We can apply cyclic shifts to the parallelepiped in any of the three directions any number of times$$$^{\text{∗}}$$$.There are $$$d_i$$$ cubes of the $$$i$$$-th color ($$$1 \le i \le k$$$). How many different parallelepipeds (with the given sides) can be formed from these cubes, no two of which can be made equal by some combination of cyclic shifts?$$$^{\text{∗}}$$$On the image: Top left shows the top view of the original parallelepiped. Lower layers will shift in the same way as the top layer. Top right shows the top view of a parallelepiped shifted to the right by $$$1$$$. Bottom left shows the top view of a parallelepiped shifted down by $$$2$$$. Bottom right shows the top view of a parallelepiped shifted to the right by $$$1$$$ and down by $$$2$$$. InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.The first line of each test case contains four integers: $$$a$$$, $$$b$$$, $$$c$$$, and $$$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$$$) — three sides of the parallelepiped and the number of colors of unit cubes.The second line of each test case contains $$$k$$$ integers $$$d_1, d_2, \ldots, d_k$$$ ($$$1 \le d_1 \le d_2 \le \ldots \le d_k \le 3 \cdot 10^6$$$) — the elements of the array $$$d$$$: the number of cubes of a given color.It is guaranteed that in each test case the sum of the elements of the array $$$d$$$ is equal to $$$a \cdot b \cdot c$$$.It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$10 ^ 6$$$.OutputFor each test case, print one integer — the number of different parallelepipeds modulo $$$998\,244\,353$$$.ExampleInput61 1 1 116 1 1 31 2 312 1 1 32 4 63 3 1 23 62 3 3 26 1272 60 96 417280 86400 120960 190080Output1
10
1160
12
1044
231490207
NoteIn the first test case, there is only one parallelepiped, which consists of one unit cube. Possible parallelepipeds in the second test case