You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

原题来自：BZOJ 3033

七夕祭上，Vani 牵着 cl 的手，在明亮的灯光和欢乐的气氛中愉快地穿行。这时，在前面忽然出现了一台太鼓达人机台，而在机台前坐着的是刚刚被精英队伍成员 XLk、Poet_shy 和 lydrainbowcat 拯救出来的的 applepi。看到两人对太鼓达人产生了兴趣，applepi 果断闪人，于是 cl 拿起鼓棒准备挑战。然而即使是在普通难度下，cl 的路人本性也充分地暴露了出来。一曲终了，不但没有过关，就连鼓都不灵了。Vani 十分过意不去，决定帮助工作人员修鼓。

鼓的主要元件是 $M$ 个围成一圈的传感器。每个传感器都有开和关两种工作状态，分别用 $1$ 和 $0$ 表示。显然，从不同的位置出发沿顺时针方向连续检查 $K$ 个传感器可以得到 $M$ 个长度为 $K$ 的 $01$ 串。Vani 知道这 $M$ 个 $01$ 串应该是互不相同的。而且鼓的设计很精密，$M$ 会取到可能的最大值。现在 Vani 已经了解到了 $K$ 的值，他希望你求出 $M$ 的值，并给出字典序最小的传感器排布方案。

输入格式

一个整数 $K$。

输出格式

一个整数 $M$ 和一个二进制串，由一个空格分隔。表示可能的最大的 $M$，以及字典序最小的排布方案，字符 0 表示关，1 表示开。你输出的串的第一个字和最后一个字是相邻的。

样例

3

8 00010111

得到的 $8$ 个 $01$ 串分别是 $000,001,010,101,011,111,110$ 和 $100$。注意前后是相邻的。长度为 $3$ 的二进制串总共只有 $8$ 种，所以 $M=8$ 一定是可能的最大值。

数据范围与提示

对于全部测试点，$2 \le K \le 11$。