P10950 Taiko no Tatsujin

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.

An integer $K$.

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.

Constraints: $2\le K\le 11$. Translated by ChatGPT 5