Hệ nhị phân (hay hệ đếm cơ số hai) là một hệ đếm dùng hai ký tự để biểu đạt một giá trị số, bằng tổng số các lũy thừa của 2. Hai ký tự đó thường là 0 và 1; chúng thường được dùng để biểu đạt hai giá trị hiệu điện thế tương ứng (có hiệu điện thế, hoặc hiệu điện thế cao là 1 và không có, hoặc thấp là 0). Do có ưu điểm tính toán đơn giản, dễ dàng thực hiện về mặt vật lý, chẳng hạn như trên các mạch điện tử, hệ nhị phân trở thành một phần kiến tạo căn bản trong các máy tính đương thời.

     Trong bài tập này bạn được cho một số nguyên dương n, bạn cần tìm và in ra danh sách các dãy nhị phân có độ dài đúng n thoả mãn điều kiện cụm "01" xuất hiện không quá 1 lần trong dãy nhị phân này.

Input:

  - Gồm một số nguyên dương n (1 ≤ n ≤ 20)

Output:

  - n dòng mỗi dòng in một dãy nhị phân độ dài n tìm được. Các dãy nhị phân in tăng dần theo thứ tự từ điển.

  - Dòng cuối cùng ghi một số nguyên dương m là số lượng dãy nhị phân tìm được.