Zeros and ones (1) P12828

Write a backtracking program to print all the combinations of z zeros and o ones such that z + o = n, for a given n.

Input

Input consists of a natural number n > 0.

Output

Print all the combinations of z zeros and o ones such that z + o = n, one per line and in lexicographical order.

Observation

Although a backtracking program is not really necessary to solve this exercise, implement it anyway for the sake of practice.