Codeforces Round 992 (Div. 2) |
---|
Finished |
Consider 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∗.
There are di cubes of the i-th color (1≤i≤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?
∗On the image:
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). The description of the test cases follows.
The first line of each test case contains four integers: a, b, c, and k (1≤a,b,c≤3⋅106; a⋅b⋅c≤3⋅106; 1≤k≤106) — three sides of the parallelepiped and the number of colors of unit cubes.
The second line of each test case contains k integers d1,d2,…,dk (1≤d1≤d2≤…≤dk≤3⋅106) — 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⋅b⋅c.
It is guaranteed that the sum of k over all test cases does not exceed 106.
For each test case, print one integer — the number of different parallelepipeds modulo 998244353.
61 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 190080
1 10 1160 12 1044 231490207
In the first test case, there is only one parallelepiped, which consists of one unit cube.
Name |
---|