Паку Чанаку дан массив \(a\) из \(n\) целых чисел. Для каждого \(i\) (\(1 \leq i \leq n\)) Пак Чанак пишет на доске одноэлементное множество \(\{a_i\}\).
После этого за одну операцию Пак Чанак может сделать следующее:
- Выбрать два различных множества \(S\) и \(T\) на доске таких, что \(S \cap T = \varnothing\) (\(S\) и \(T\) не имеют общих элементов).
- Стереть \(S\) и \(T\) с доски и записать \(S \cup T\) (объединение \(S\) и \(T\)) на доску.
Выполнив ноль или более операций, Пак Чанак построит мультимножество \(M\), содержащее размеры всех множеств, написанных на доске. Другими словами, каждый элемент в \(M\) соответствует размеру некоторого множества после операций.
Сколько различных\(^\dagger\) мультимножеств \(M\) может быть получено таким процессом? Так как ответ может быть большим, выведите его по модулю \(998\,244\,353\).
\(^\dagger\) Мультимножества \(B\) и \(C\) различны тогда и только тогда, когда существует значение \(k\) такое, что количество элементов со значением \(k\) в \(B\) отличается от количества элементов со значением \(k\) в \(C\).
Выходные данные
Выведите количество различных мультимножеств \(M\) по модулю \(998\,244\,353\).
Примечание
В первом примере возможные мультимножества \(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\}\), \(\{2\}\), \(\{1\}\), \(\{4\}\) и \(\{3\}\).
- Применяем операцию ко множествам \(\{1\}\) и \(\{3\}\). Теперь множества на доске имеют вид \(\{1\}\), \(\{1\}\), \(\{2\}\), \(\{4\}\) и \(\{1,3\}\).
- Применяем операцию ко множествам \(\{2\}\) and \(\{4\}\). Теперь множества на доске имеют вид \(\{1\}\), \(\{1\}\), \(\{1,3\}\) и \(\{2,4\}\).
- Применяем операцию ко множествам \(\{1,3\}\) and \(\{2,4\}\). Теперь множества на доске имеют вид \(\{1\}\), \(\{1\}\) и \(\{1,2,3,4\}\).
- Полученное мультимножество \(M\) имеет вид \(\{1,1,4\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 1 2 1 4 3
|
7
|
|
2
|
7
3 5 4 3 7 4 5
|
11
|