原題來自：BZOJ 3033

七夕祭上，Vani 牽著 cl 的手，在明亮的燈光和歡樂的氣氛中愉快地穿行。這時(shí)，在前面忽然出現(xiàn)了一臺(tái)太鼓達(dá)人機(jī)臺(tái)，而在機(jī)臺(tái)前坐著的是剛剛被精英隊(duì)伍成員 XLk、Poet_shy 和 lydrainbowcat 拯救出來的的 applepi?？吹絻扇藢?duì)太鼓達(dá)人產(chǎn)生了興趣，applepi 果斷閃人，于是 cl 拿起鼓棒準(zhǔn)備挑戰(zhàn)。然而即使是在普通難度下，cl 的路人本性也充分地暴露了出來。一曲終了，不但沒有過關(guān)，就連鼓都不靈了。Vani 十分過意不去，決定幫助工作人員修鼓。

鼓的主要元件是 MM 個(gè)圍成一圈的傳感器。每個(gè)傳感器都有開和關(guān)兩種工作狀態(tài)，分別用 1 和 0 表示。顯然，從不同的位置出發(fā)沿順時(shí)針方向連續(xù)檢查 K 個(gè)傳感器可以得到 M 個(gè)長度為 K 的 01 串。Vani 知道這 M 個(gè) 01 串應(yīng)該是互不相同的。而且鼓的設(shè)計(jì)很精密，M 會(huì)取到可能的最大值?，F(xiàn)在 Vani 已經(jīng)了解到了 K 的值，他希望你求出 M 的值，并給出字典序最小的傳感器排布方案。

一個(gè)整數(shù) K。

一個(gè)整數(shù) M 和一個(gè)二進(jìn)制串，由一個(gè)空格分隔。表示可能的最大的 M，以及字典序最小的排布方案，字符0表示關(guān)，1表示開。你輸出的串的第一個(gè)字和最后一個(gè)字是相鄰的。

樣例解釋:

得到的 8 個(gè) 01 串分別是 000,001,010,101,011,111,110 和 100。注意前后是相鄰的。長度為 3 的二進(jìn)制串總共只有 8 種，所以 M=8 一定是可能的最大值。

數(shù)據(jù)范圍與提示：

對(duì)于全部測試點(diǎn)，2≤K≤11。

信息學(xué)一本通 圖論