Yêu cầu

Cho số nguyên N. Hãy in tất cả các xâu nhị phân độ dài N không chứa hai bit 1 đứng kề nhau, theo thứ tự từ điển.

Dữ liệu vào

Một số nguyên N.

Dữ liệu ra

Mỗi xâu thỏa mãn in trên một dòng.

Ràng buộc

1 ≤ N ≤ 16.

Ví dụ

3

000
001
010
100
101