De Bruijn sequences (1) P85110

A binary de Bruijn sequence of order n is a cyclic sequence of zeros and ones such that every possible subsequence of n consecutive digits appears exactly once. Please compute the lexicographically smallest de Bruijn sequence of order n.

Input

Input consists of several cases, each with an integer number n between 1 and ‍15.

Output

For every case, print the lexicographically smallest de Bruijn sequence of order n.

Hint

A “reasonable” backtracking algorithm should be fast enough to get this problem accepted.