Дана последовательность \(a_1,\dots,a_n\) длины \(n\), изначально все её элементы — пустые. Над последовательностью совершают \(n\) обновлений, в каждом из которых один из элементов \(a\) становится некоторым числом, таким образом, что после всех обновлений \(a\) становится перестановкой \(1,2,\dots,n\).
После каждого обновления найдите число способов (по модулю \(998\,244\,353\)) заполнить остающиеся пустые места в \(a\) так, чтобы \(a\) стала перестановкой \(1,2,\dots,n\), причём длины всех циклов в \(a\) стали кратны \(3\).
Перестановкой \(1,2,\dots,n\) является последовательность длины \(n\), состоящая из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Циклом в перестановке \(a\) называется последовательность попарно различных чисел \((i_1,\dots,i_k)\), такая что \(i_2 = a_{i_1},i_3 = a_{i_2},\dots,i_k = a_{i_{k-1}},i_1 = a_{i_k}\). Длина этого цикла равна числу \(k\), которое кратно \(3\), если и только если \(k \equiv 0 \pmod 3\).
Выходные данные
Выведите \(n\) строк: число способов (по модулю \(998\,244\,353\)) после \(1,2,\dots,n\) обновлений.
Примечание
В первом примере, скажем, после \(3\)-го обновления есть \(3\) способа заполнить последовательность \(a = [4,\_,2,5,\_,\_]\):
- \([4,1,2,5,6,3]\): имеем один цикл \((1\,4\,5\,6\,3\,2)\) длины \(6\).
- \([4,6,2,5,1,3]\): имеем два цикла \((1\,4\,5)\) и \((2\,6\,3)\), с длинами \(3\) и \(3\).
- \([4,6,2,5,3,1]\): имеем один цикл \((1\,4\,5\,3\,2\,6)\) длины \(6\).
Во втором примере первое же обновление создаёт цикл длины \(1\), так что нет ни одного способа сделать так, чтобы длины всех циклов были кратны \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 2
1 4
4 5
2 6
5 1
6 3
|
32
8
3
2
1
1
|
|
2
|
3
1 1
2 3
3 2
|
0
0
0
|
|
3
|
18
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 1
|
671571067
353924552
521242461
678960117
896896000
68992000
6272000
627200
62720
7840
1120
160
32
8
2
1
1
1
|