Cirno подготовила \(n\) массивов длины \(n\) каждый. Каждый массив — это перестановка из \(n\) целых чисел от \(1\) до \(n\). Эти массивы специальные: для всех \(1 \leq i \leq n\), если мы возьмем \(i\)-й элемент каждого массива и построим другой массив длины \(n\), состоящий из этих элементов, получившийся массив также будет перестановкой \(n\) чисел от \(1\) до \(n\). Другими словами, если эти \(n\) массивов расположить друг под другом, образовав матрицу с \(n\) строками и \(n\) столбцами, эта матрица будет латинским квадратом.
После этого Cirno добавила дополнительные \(n\) массивов, каждый массив также является перестановкой из \(n\) целых чисел от \(1\) до \(n\). Для всех \(1 \leq i \leq n\) существует хотя бы одна позиция \(1 \leq k \leq n\), такая что для \(i\)-го и \((n + i)\)-го массивов \(k\)-е элементы совпадают. Обратите внимание, что массивы с индексами от \(n + 1\) до \(2n\) не обязаны образовывать латинский квадрат.
Также Cirno убедилась, что среди \(2n\) массивов никакие два не равны, то есть для всех пар индексов \(1 \leq i < j \leq 2n\) существует хотя бы одна позиция \(1 \leq k \leq n\), такая что в \(i\)-м и \(j\)-м массивах \(k\)-е элементы различны.
В конце Cirno произвольно поменяла порядок, в котором расположены подготовленные \(2n\) массивов.
AquaMoon называет подмножество всех \(2n\) массивов размера \(n\) хорошим, если эти массивы образуют латинский квадрат.
AquaMoon хочет узнать, сколько хороших подмножеств существует. Поскольку это количество может быть очень большим, найдите его по модулю \(998\,244\,353\). Также она хочет найти любое хорошее подмножество. Можете ли вы помочь ей?
Выходные данные
Для каждого набора входных данных выведите две строки.
В первой строке выведите количество хороших подмножеств по модулю \(998\,244\,353\).
Во второй строке выведите \(n\) индексов от \(1\) до \(2n\) — индексы \(n\) массивов, которые образуют хорошее подмножество (вы можете вывести их в любом порядке). Если существует несколько возможных ответов — выведите любой.
Примечание
В первом наборе входных данных количество хороших подмножеств равно \(1\). Единственное такое подмножество это подмножество массивов с индексами \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\).
Во втором наборе входных данных количество хороших подмножеств равно \(2\). Эти подмножества это \(1\), \(3\), \(5\), \(6\), \(10\), а также \(2\), \(4\), \(7\), \(8\), \(9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
7
1 2 3 4 5 6 7
2 3 4 5 6 7 1
3 4 5 6 7 1 2
4 5 6 7 1 2 3
5 6 7 1 2 3 4
6 7 1 2 3 4 5
7 1 2 3 4 5 6
1 2 3 4 5 7 6
1 3 4 5 6 7 2
1 4 5 6 7 3 2
1 5 6 7 4 2 3
1 6 7 5 2 3 4
1 7 6 2 3 4 5
1 7 2 3 4 5 6
5
4 5 1 2 3
3 5 2 4 1
1 2 3 4 5
5 2 4 1 3
3 4 5 1 2
2 3 4 5 1
1 3 5 2 4
4 1 3 5 2
2 4 1 3 5
5 1 2 3 4
6
2 3 4 5 6 1
3 1 2 6 4 5
6 1 2 3 4 5
5 6 1 3 2 4
4 3 6 5 2 1
5 6 1 2 3 4
4 5 6 1 2 3
3 4 5 6 1 2
1 2 3 4 5 6
2 5 4 1 6 3
3 2 5 4 1 6
1 4 3 6 5 2
|
1
1 2 3 4 5 6 7
2
1 3 5 6 10
4
1 3 6 7 8 9
|