시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 256 MB0000.000%

문제

A path in the $n$-dimensional set $\{0, 1\}^n$ is a sequence of $n$-dimensional points $x_1, x_2, \ldots, x_k \in \{0, 1\}^n$ such that, for each $i$ ($1 \le i \le k - 1$), points $x_i$ and $x_{i + 1}$ differ in exactly one coordinate, and all the points $x_1, \ldots, x_k$ are distinct. The length of the path $x_1, \ldots, x_k$ is $k$.

A path  $x_1, \ldots, x_k$ is imperfect if there exists a shorter path $y_1, \ldots, y_{\ell}$ which leads from the first to the last point of this path and consists of a subset of the same points. In other words, $\{y_1, \ldots, y_{\ell}\} \subseteq \{x_1, \ldots, x_k\}$, $x_1 = y_1$, $x_k = y_{\ell}$ and $\ell < k$. If a path is not imperfect, it is perfect.

Your task is to find the longest perfect path in the set $\{0, 1\}^n$.

입력

The only line contains a single integer $n$ ($1 \le n \le 6$).

출력

On the first line, print $L$, the length of the path. On the next $L$ lines, print the description of the path $x_1, \ldots, x_L$: $i$-th of these lines must contain $n$ characters (zeroes and ones) describing the point $x_i$.

It is easy to see that there are multiple longest perfect paths. Print any one of them.

예제 입력 1

2

예제 출력 1

3
00
01
11

예제 입력 2

3

예제 출력 2

5
000
001
011
111
110

예제 입력 3

4

예제 출력 3

8
0000
0001
0011
0111
0110
1110
1100
1101