19787번 - Взлом шифра 스페셜 저지다국어

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

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

Более формально: предположим, что Алан нажал на кнопки $k$ раз. Пусть $a_i$ ($1 \le i \le k$) --- номер кнопки, которую Алан нажал $i$ по счету, а $b_1, b_2, \ldots, b_n$ --- секретная перестановка. Тогда замок открывается, если существует такое число $x$ ($1 \le x \le k - n + 1$), что $b_1 = a_x$, $b_2 = a_{x+1}$, \dots, $b_n = a_{x+n-1}$.

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

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

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

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