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