А вот первые слова маленького Эхаба: «Дано целое число \(n\), найдите самую длинную подпоследовательность массива \([1,2, \ldots, n-1]\), произведение элементов которой равно \(1\) по модулю \(n\)». Решите эту задачу.
Последовательность \(b\) является подпоследовательностью массива \(a\), если \(b\) может быть получена из \(a\) удалением нескольких (возможно, всех) элементов. Произведение элементов пустой подпоследовательности равно \(1\).
Выходные данные
В первой строке выведите длину найденной подпоследовательности.
Во второй строке выведите элементы подпоследовательности в возрастающем порядке.
Если существует несколько ответов, выведите любой.
Примечание
В первом примере произведение элементов равно \(6\), что равно \(1\) по модулю \(5\). Единственная более длинная последовательность это \([1,2,3,4]\). Произведение ее элементов равно \(24\), что равно \(4\) по модулю \(5\). Поэтому, ответ это \([1,2,3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
|
3
1 2 3
|
|
2
|
8
|
4
1 3 5 7
|