В Берляндском Биологическом Университете (ББУ) занимаются изучением бактерий. Известно, что поведение бактерии определяется строением ее ДНК. В этой задаче будем считать, что ДНК бактерии — это строка, состоящая из нулей и единиц.

Недавно ученые ББУ открыли новый вид бактерий, основная особенность которого заключается в том, что при делении клетки ее ДНК не реплицируется, а также делится пополам. А именно, пусть ДНК исходной клетки задается некоторой строкой $$$S=s_1s_2\ldots s_k$$$ четной длины $$$k$$$ ($$$s_i$$$ обозначет $$$i$$$-й символ строки $$$S$$$ и равен либо $$$0$$$, либо $$$1$$$). Тогда в результате деления будут получены клетки с ДНК, равными $$$s_1s_2\ldots s_{\frac{k}{2}}$$$ и $$$s_{\frac{k}{2}+1}\ldots s_{k-1}s_k$$$, соответственно.

Для исследования ученые планируют взять бактерию, ДНК которой будет иметь длину $$$2^n$$$. Исследование состоит из $$$n+1$$$ шага, в конце каждого из которых, кроме последнего, каждая имеющаяся в данный момент бактерия делится. Так, на первом шаге будет всего одна бактерия с ДНК длиной $$$2^n$$$, на втором — две бактерии с ДНК с длинами $$$2^{n-1}$$$ каждая и так далее. Наконец, на $$$n+1$$$ шаге будет $$$2^n$$$ бактерий, ДНК каждой из которых будет состоять лишь из одного символа.

Разумеется, изучать бактерии с одинаковыми ДНК неинтересно. Определите, какой должна быть ДНК у первой бактерии, чтобы в ходе исследования было получено как можно больше различных ДНК.