암호 해독

Алан은 암호와 코드 자물쇠를 여는 것을 좋아한다. 이번에는 그가 유난히 복잡한 자물쇠를 만났는데, 열쇠를 찾지 못해 가능한 모든 조합을 시도해서 열쇠를 알아내기로 했다.

자물쇠는 정수 1부터 $n$까지 번호가 매겨진 $n$개의 버튼으로 이루어져 있다. 자물쇠는 연속한 $n$번의 버튼 누름이 어떤 비밀 순열을 이루면 열린다. 자물쇠의 버튼은 한 번에 하나씩 눌러야 하며, 두 개 이상의 버튼을 동시에 누를 수 없다.

더 형식적으로: Алан이 버튼을 $k$번 눌렀다고 하자. $a\_i$ ($1 \le i \le k$)를 Алан이 $i$번째로 누른 버튼의 번호, $b\_1, b\_2, \ldots, b\_n$을 비밀 순열이라고 하자. 그러면 자물쇠는 $b\_1 = a\_x$, $b\_2 = a\_{x+1}$, ..., $b\_n = a\_{x+n-1}$인 $x$ ($1 \le x \le k - 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$에 대해 존재함이 보장된다.