Problem Description

The drum in Taiko no Tatsujin is broken, and now vani is here to fix it.

The main component of the drum is $M$ sensors arranged in a circle.

Each sensor has two working states, on and off, denoted by $1$ and $0$, respectively.

Obviously, starting from different positions and checking $K$ consecutive sensors clockwise, you can obtain $M$ binary strings of length $K$.

Vani knows that these $M$ binary strings should be pairwise distinct.

Also, the drum is very precisely designed, so $M$ takes the maximum possible value.

Now Vani already knows the value of $K$. He wants you to find the value of $M$ and give the lexicographically smallest sensor arrangement.

Input Format

An integer $K$.

Output Format

An integer and a binary string, separated by a space, representing the maximum possible $M$ and the lexicographically smallest arrangement.

Character $0$ means off, and $1$ means on. In the string you output, the first character and the last character are adjacent.

3

8 00010111

Hint

Constraints: $2\le K\le 11$.

Translated by ChatGPT 5