De Bruijn Drum Sensor Configuration

Vani is repairing a damaged drum in which the key component is a set of $M$ sensors arranged in a circle. Each sensor has two states: on (1) and off (0). If you start from every sensor and read $K$ consecutive sensors in the clockwise direction (wrapping around the circle), you obtain $M$ binary strings of length $K$. Vani knows that these $M$ strings must all be distinct, and furthermore the drum design is so precise that $M$ takes on the maximum possible value. Given $K$, your task is to compute $M$ and output the lexicographically smallest sensor configuration that satisfies these properties.

Note: A valid configuration is a circular binary sequence such that every possible binary string of length $K$ (there are $2^K$ of them) appears exactly once as a contiguous subsequence. This sequence is known as a de Bruijn sequence for $K$-tuples over the alphabet {0, 1}.

inputFormat

The input consists of a single integer $K$ ($1 \le K \le 20$) representing the length of the binary strings.

outputFormat

Output two lines. The first line contains the integer $M$, which is $2^K$. The second line contains the lexicographically smallest de Bruijn sequence (a binary string of length $M$) representing the sensor configuration.

sample

1

2
01