Злам шифру
Алан захоплюється розгадуванням шифрів і кодових замків. Цього разу він зіткнувся з надзвичайно складним замком, для якого не зміг знайти ключ, тому вирішив перебрати всі можливі комбінації, щоб дізнатися код.
Замок має 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.