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

Паку Чанаку дан массив $$$a$$$ из $$$n$$$ целых чисел. Для каждого $$$i$$$ ($$$1 \leq i \leq n$$$) Пак Чанак пишет на доске одноэлементное множество $$$\{a_i\}$$$.

После этого за одну операцию Пак Чанак может сделать следующее:

  1. Выбрать два различных множества $$$S$$$ и $$$T$$$ на доске таких, что $$$S \cap T = \varnothing$$$ ($$$S$$$ и $$$T$$$ не имеют общих элементов).
  2. Стереть $$$S$$$ и $$$T$$$ с доски и записать $$$S \cup T$$$ (объединение $$$S$$$ и $$$T$$$) на доску.

Выполнив ноль или более операций, Пак Чанак построит мультимножество $$$M$$$, содержащее размеры всех множеств, написанных на доске. Другими словами, каждый элемент в $$$M$$$ соответствует размеру некоторого множества после операций.

Сколько различных$$$^\dagger$$$ мультимножеств $$$M$$$ может быть получено таким процессом? Так как ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.

$$$^\dagger$$$ Мультимножества $$$B$$$ и $$$C$$$ различны тогда и только тогда, когда существует значение $$$k$$$ такое, что количество элементов со значением $$$k$$$ в $$$B$$$ отличается от количества элементов со значением $$$k$$$ в $$$C$$$.

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

Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 2000$$$).

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

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

Выведите количество различных мультимножеств $$$M$$$ по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
6
1 1 2 1 4 3
Выходные данные
7
Входные данные
7
3 5 4 3 7 4 5
Выходные данные
11
Примечание

В первом примере возможные мультимножества $$$M$$$ таковы: $$$\{1,1,1,1,1,1\}$$$, $$$\{1,1,1,1,2\}$$$, $$$\{1,1,1,3\}$$$, $$$\{1,1,2,2\}$$$, $$$\{1,1,4\}$$$, $$$\{1,2,3\}$$$ и $$$\{2,2,2\}$$$.

В качестве примера рассмотрим возможную последовательность операций.

  1. Вначале множества имеют вид $$$\{1\}$$$, $$$\{1\}$$$, $$$\{2\}$$$, $$$\{1\}$$$, $$$\{4\}$$$ и $$$\{3\}$$$.
  2. Применяем операцию ко множествам $$$\{1\}$$$ и $$$\{3\}$$$. Теперь множества на доске имеют вид $$$\{1\}$$$, $$$\{1\}$$$, $$$\{2\}$$$, $$$\{4\}$$$ и $$$\{1,3\}$$$.
  3. Применяем операцию ко множествам $$$\{2\}$$$ and $$$\{4\}$$$. Теперь множества на доске имеют вид $$$\{1\}$$$, $$$\{1\}$$$, $$$\{1,3\}$$$ и $$$\{2,4\}$$$.
  4. Применяем операцию ко множествам $$$\{1,3\}$$$ and $$$\{2,4\}$$$. Теперь множества на доске имеют вид $$$\{1\}$$$, $$$\{1\}$$$ и $$$\{1,2,3,4\}$$$.
  5. Полученное мультимножество $$$M$$$ имеет вид $$$\{1,1,4\}$$$.