F. Количество кубов
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим прямой параллелепипед с размерами сторон $$$a$$$, $$$b$$$ и $$$c$$$, состоящий из единичных кубиков $$$k$$$ различных цветов. Мы можем делать циклические сдвиги параллелепипеда в любом измерении и в любой комбинации$$$^{\text{∗}}$$$.

Имеется $$$d_i$$$ кубиков $$$i$$$-го цвета ($$$1 \le i \le k$$$). Сколько можно составить из этих кубиков различных параллелепипедов с данными размерами сторон, никакие два из которых нельзя совместить комбинацией сдвигов?

$$$^{\text{∗}}$$$На рисунке:

  • Слева-вверху показан вид сверху у изначального параллелепипеда. Нижние слои будут сдвигаться по аналогии с верхним.
  • Справа-вверху показан вид сверху у параллелепипеда, сдвинутого направо на $$$1$$$.
  • Слева-внизу показан вид сверху у параллелепипеда, сдвинутого вниз на $$$2$$$.
  • Справа-внизу показан вид сверху у параллелепипеда, сдвинутого направо на $$$1$$$ и вниз на $$$2$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Пример
Входные данные
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
10
1160
12
1044
231490207
Примечание

В первом наборе существует только один параллелепипед, состоящий из одного единичного куба.

Возможные параллелепипеды во втором наборе