Description

Original source: BZOJ 3033

At the Tanabata festival, Vani held cl's hand and walked happily through the bright lights and joyful atmosphere. Suddenly, a Taiko no Tatsujin arcade machine appeared ahead, with applepi sitting in front of it, who had just been rescued by the elite team members XLk, Poet_shy, and lydrainbowcat. Seeing the two become interested in Taiko no Tatsujin, applepi quickly left, and cl picked up the drumsticks to take on the challenge. However, even on normal difficulty, cl's amateur nature was fully exposed. By the end of the song, not only had they failed to clear the level, but the drum itself stopped working. Feeling very sorry, Vani decided to help the staff repair the drum.

The main component of the drum is $M$ sensors arranged in a circle. Each sensor has two working states: on and off, represented by $1$ and $0$, respectively. Clearly, starting from different positions and checking $K$ consecutive sensors clockwise yields $M$ binary strings of length $K$. Vani knows that these $M$ strings should all be distinct. Moreover, the drum is designed so precisely that $M$ will take the maximum possible value. Now that Vani has learned the value of $K$, he asks you to determine the value of $M$ and provide the sensor arrangement with the smallest lexicographical order.

Input Format

An integer $K$.

Output Format

An integer $M$ and a binary string, separated by a space. This represents the maximum possible $M$ and the arrangement with the smallest lexicographical order, where the character 0 denotes off and 1 denotes on. The first and last characters of the string you output are adjacent.

Sample 1

The resulting 8 binary strings are $000,001,010,101,011,111,110$, and $100$. Note that the beginning and end are adjacent. There are only 8 possible binary strings of length 3, so $M=8$ must be the maximum possible value.

3

8 00010111

Data Range and Hint

For all test cases, $2 \le K \le 11$.