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 \(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 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.

Yêu cầu:

Hãy liệt kê tất cả các dãy nhị phân độ dài đúng \(n\) 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.

Dữ liệu vào Specification

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

Dữ liệu ra Specification

• Dòng đầu tiên ghi một số nguyên dương \(m\) 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 \(n\) tìm được. Các dãy nhị phân in tăng dần theo thứ tự từ điển.

Sample Input

3

Sample Output

5
000
001
010
100
101