Given a positive integer N, please output all binary numbers who has N digits but the one bits are more than or equals to the 0 bits for all its prefix of the number; please note that left most digit has to be one.
for example, given N=4, here is the answer:

1111
1110
1101
1100
1011
1010
But 0010 is not the answer. and 1001 is not the answer; 
1011 is the answer because the one bits are more or equals to zero bits in all it prefix 1, 10, 101 and 1011;
1001 is not the answer because its prefix 100 violates the constraint.

The first line contains one integer N 
$ 1 \leq N \leq 20 $

Output all the answers, one in a line in descending order.