B. Совет мрамора
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан мультисет $$$a$$$, который состоит из $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$. Вы хотите сгенерировать новый мультисет $$$s$$$ с помощью следующей процедуры:

  • Разделите $$$a$$$ на любое количество непустых мультисетов $$$x_1,x_2,\ldots,x_k$$$, так что каждый элемент $$$a$$$ принадлежит ровно одному из этих мультисетов.
  • Изначально $$$s$$$ пуст. Из каждого $$$x_i$$$ выберите одну из его мод$$$^{\text{∗}}$$$ и вставьте её в $$$s$$$.

Пожалуйста, посчитайте количество различных мультисетов $$$s$$$, которые могут быть сгенерированы с помощью этой процедуры, по модулю $$$998\,244\,353$$$.

Обратите внимание, что подсчитывается количество различных мультисетов, что означает, что порядок элементов не имеет значения. Однако количество каждого элемента имеет значение, т.е. $$$\{1,1,2\},\{1,2\},\{1,1,2,2\}$$$ считаются различными.

$$$^{\text{∗}}$$$Мода мультисета определяется как элемент, который появляется чаще всего; если несколько элементов имеют максимальное количество, то все они считаются модами.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le5000$$$) — размер мультисета $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую одно целое число — количество различных мультисетов, которые вы можете получить, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
3
1 2 3
3
1 1 1
3
1 2 2
10
1 1 1 1 2 2 2 3 3 4
10
1 1 1 2 2 2 3 3 3 4
Выходные данные
7
3
4
111
126
Примечание

В первом наборе входных данных любое непустое подмножество $$$\{1,2,3\}$$$ может быть достигнуто, всего $$$7$$$ мультисетов.

В третьем наборе входных данных мы можем сгенерировать $$$4$$$ различных мультисета:

  • Разделите элементы на множество $$$\{1,2,2\}$$$, в результате получится мультисет $$$\{2\}$$$.
  • Разделите элементы на множества $$$\{1,2\},\{2\}$$$, в результате получится мультисет $$$\{2,2\}$$$.
  • Разделите элементы на множества $$$\{1\},\{2,2\}$$$, в результате получится мультисет $$$\{1,2\}$$$.
  • Разделите элементы на множества $$$\{1\},\{2\},\{2\}$$$, в результате получится мультисет $$$\{1,2,2\}$$$.

Можно доказать, что другие мультисеты невозможны.