Задача D. Взлом шифра ≡

Условие

Алан любит вскрывать шифры и кодовые замки. На этот раз ему попался необычайно сложный замок, найти ключ к которому Алану не удалось, поэтому он решил перебрать все возможные комбинации, чтобы узнать ключ.

Замок представляет собой n кнопок, пронумерованных целыми числами от 1 до n. Замок открывается только тогда, когда какие-то последовательные n нажатий на кнопки образуют некоторую секретную перестановку. Кнопки замка следует нажимать по очереди, нажать одновременно две или более кнопки нельзя.

Более формально: предположим, что Алан нажал на кнопки k раз. Пусть a_i (1 ≤ i ≤ k) — номер кнопки, которую Алан нажал i по счету, а b₁, b₂, …, b_n — секретная перестановка. Тогда замок открывается, если существует такое число x (1 ≤ x ≤ k − n + 1), что b₁ = a_x, b₂ = a_x+1, …, b_n = a_x+n−1.

Алан хочет придумать такую универсальную последовательность нажатий, что при нажатии кнопок в такой последовательности замок откроется для любой секретной перестановки. Также Алан хочет, чтобы эта последовательность не была слишком длинной, а именно, ее длина не превышала 2 n!, где n! = 1 ⋅ 2 ⋅ … ⋅ n. Например, для n = 3 длина последовательности не должна превышать 12.

Помогите Алану найти такую последовательность.

Формат входного файла

В единственной строке входного файла находится целое число n (1 ≤ n ≤ 9) — количество кнопок на кодовом замке.

Формат выходного файла

В первой строке выходного файла выведите число k (0 ≤ k ≤ 2 n!) — длину универсальной последовательности. Во второй строке выведите k целых чисел a_i, разделенных пробелами (1 ≤ a_i ≤ n) — порядок, в котором следует нажимать кнопки. Обратите внимание, что достаточно вывести любую последовательность длины не более 2 n!, минимизировать длину не нужно. Гарантируется, что такая последовательность существует для любого n.

Примеры тестов

2

3
1 2 1

3

10
1 2 3 1 3 2 1 3 1 2