Hệ nhị phân (hay hệ đếm cơ số 2) là một hệ đếm dùng 2 ký tự để biểu đạt một giá trị số, bằng tổng số các lũy thừa của 2. Người ta thường sử dụng 2 ký tự đó 0 và 1. Trong bài toán này khi liệt kê ra dãy nhị phân Mr Toàn muốn bạn hiểu rõ hơn quy trình đệ quy sinh ra các dãy đó nên thêm vào một số điều kiện để hạn chế số lượng dãy nhị phân in ra. Trong bài tập này bạn được cho một số nguyên dương nn, bạn cần tìm và in ra danh sách các dãy nhị phân có độ dài đúng nn thoả mãn điều kiện không có hai số 1 đứng cạnh nhau. Hơn thế nữa bạn cần in ra số lượng các dãy đó trước khi liệt kê cụ thể các dãy.

Hãy liệt kê tất cả các dãy nhị phân độ dài đúng nn thoả mãn điều kiện không có hai số 1 đứng cạnh nhau theo thứ tự từ điển tăng dần.

• Gồm 1 dòng là số nguyên nn (0<n≤20)(0<n≤20).

• Dòng đầu tiên ghi một số nguyên dương mm là số lượng dãy nhị phân tìm được.
• Mỗi dòng tiếp theo in một dãy nhị phân độ dài nn tìm được. Các dãy nhị phân in tăng dần theo thứ tự từ điển.