Mật mã an toàn

Để tăng cường bảo mật, Thám tử K quyết định rằng các chuỗi nhị phân không được phép có hai số \(1\) nào đứng kề nhau (ví dụ: \(11\) bị cấm). Hãy sử dụng đệ quy để liệt kê tất cả các chuỗi nhị phân có độ dài \(N\) thỏa mãn điều kiện an toàn này.

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 15\)).

Output

In ra tất cả các chuỗi nhị phân thỏa mãn, mỗi chuỗi trên một dòng, theo thứ tự từ điển tăng dần.

Example

Test 1

Input

Output

0
1

Test 2

Input

Output

00
01
10

Test 3

Input

Output

Thông tin bài

Điểm:

100

Thời gian:

1.0s

Bộ nhớ:

256M

Input:

bàn phím

Output:

màn hình

Ngày tạo:

02/08/2026

Tác giả:

root

Điều hướng chính

Ngôn ngữ

Phím tắt

Input

Output

Example

Bình luận