Найдите количество способов разбить массив \(a\) из \(n\) целых чисел на произвольное количество непересекающихся непустых подотрезков так, чтобы для каждого подотрезка существовало не более \(k\) различных чисел, которые встречаются ровно один раз.
Так как ответ может быть очень большим, выведите остаток от деления ответа на \(998\,244\,353\).
Выходные данные
Первая и единственная строка вывода должна содержать количество способов разбить элементы массива \(a\) по модулю \(998\,244\,353\).
Примечание
В первом примере возможных разбиений три:
- \([[1], [1], [2]]\)
- \([[1, 1], [2]]\)
- \([[1, 1, 2]]\)
Разбиение \([[1], [1, 2]]\) невозможно, потому что два целых числа встречаются ровно один раз на отрезке \([1, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
1 1 2
|
3
|
|
2
|
5 2
1 1 2 1 3
|
14
|
|
3
|
5 5
1 2 3 4 5
|
16
|