Trong bài toán thiết kế cấu hình nhị phân, người ta cần sinh ra tất cả các chuỗi độ dài \(N\) chỉ chứa các ký tự 0 và 1. Hãy lập trình sử dụng đệ quy quay lui (backtracking) để liệt kê toàn bộ các chuỗi nhị phân độ dài \(N\) theo thứ tự từ điển tăng dần.

Định dạng đầu vào

• Một dòng duy nhất chứa số nguyên dương \(N\) (\(1 \le N \le 20\)).

Định dạng đầu ra

• Liệt kê mỗi chuỗi nhị phân trên một dòng theo đúng thứ tự từ điển.

Ví dụ

Input:

3

Output:

000
001
010
011
100
101
110
111