Обратите внимание что единственные различия между версиями это \(n\) и ограничения по времени. Вы можете взламывать, только если обе версии решены.
Слайм интересуется последовательностями. Он определил хорошие последовательности \(p\) длины \(n\) из натуральных чисел следующим образом:
- Для каждого \(k>1\), которое встречается в \(p\), должна существовать хотя бы одна пара индексов \(i,j\), такая что \(1 \leq i < j \leq n\), \(p_i = k - 1\) и \(p_j = k\).
Для данного целого числа \(n\) множество хороших последовательностей длины \(n\) это \(s_n\). Для фиксированного целого числа \(k\) и последовательности \(p\), обозначим за \(f_p(k)\) количество раз, которое \(k\) встречается в \(p\). Для каждого \(k\) от \(1\) до \(n\), Слайм хочет знать следующее значение:
\(\)\left(\sum_{p\in s_n} f_p(k)\right)\ \textrm{mod}\ 998\,244\,353\(\)
Выходные данные
Выведите \(n\) целых чисел, \(i\)-е из них должно быть равно \(\left(\sum_{p\in s_n} f_p(i)\right)\ \textrm{mod}\ 998\,244\,353\).
Примечание
В первом примере \(s=\{[1,1],[1,2]\}\).
Во втором примере \(s=\{[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]\}\).
В третьем примере \(s=\{[1]\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
|
3 1
|
|
2
|
3
|
10 7 1
|
|
3
|
1
|
1
|