Взлом шифра
Алан любит вскрывать шифры и кодовые замки. На этот раз ему попался необычайно сложный замок, найти ключ к которому Алану не удалось, поэтому он решил перебрать все возможные комбинации, чтобы узнать ключ.
Замок представляет собой n кнопок, пронумерованных целыми числами от 1 до n. Замок открывается только тогда, когда какие-то последовательные n нажатий на кнопки образуют некоторую секретную перестановку. Кнопки замка следует нажимать по очереди, нажать одновременно две или более кнопки нельзя.
Более формально: предположим, что Алан нажал на кнопки k раз. Пусть a_i (1 ≤ i ≤ k) — номер кнопки, которую Алан нажал i по счету, а b_1, b_2, ..., b_n — секретная перестановка. Тогда замок открывается, если существует такое число x (1 ≤ x ≤ k − n + 1), что b_1 = a_x, b_2 = a_{x+1}, ..., b_n = a_{x+n−1}.
Алан хочет придумать такую универсальную последовательность нажатий, что при нажатии кнопок в такой последовательности замок откроется для любой секретной перестановки. Также Алан хочет, чтобы эта последовательность не была слишком длинной, а именно, ее длина не превышала 2n!, где n! = 1 · 2 · ... · n. Например, для n = 3 длина последовательности не должна превышать 12.
Помогите Алану найти такую последовательность.
Входные данные
В единственной строке входного файла находится целое число n (1 ≤ n ≤ 9) — количество кнопок на кодовом замке.
Выходные данные
В первой строке выходного файла выведите число k (0 ≤ k ≤ 2n!) — длину универсальной последовательности. Во второй строке выведите k целых чисел a_i, разделенных пробелами (1 ≤ a_i ≤ n) — порядок, в котором следует нажимать кнопки. Обратите внимание, что достаточно вывести любую последовательность длины не более 2n!, минимизировать длину не нужно. Гарантируется, что такая последовательность существует для любого n.