Công ty ABC sử dụng hệ thống thẻ từ để cho phép nhân viên ra vào tòa nhà. Mỗi thẻ được gắn với một mã nhị phân độ dài ~n~ (chỉ gồm các số 0 và 1), tượng trưng cho quyền truy cập theo từng khu vực. Mỗi bit trong dãy nhị phân đại diện cho quyền truy cập vào một khu vực cụ thể: 1 nghĩa là có quyền truy cập, 0 nghĩa là không có quyền truy cập.

Ví dụ: Với mã nhị phân 1010, nhân viên được vào khu 1 và 3, nhưng không được vào khu 2 và 4.

Ban quản lý muốn kiểm tra toàn bộ các mã truy cập nhằm thiết kế hệ thống quản lý truy cập hợp lý và kiểm tra độ bao phủ của các quyền truy cập.

Yêu cầu: Hãy liệt kê tất cả các dãy nhị phân độ dài ~n~, đại diện cho mọi mã truy cập của thẻ ra vào.

Input

• Nhập từ bàn phím số nguyên dương ~n~ (~2 \le n \le 17~).

Output

• Thông báo ra màn hình tất cả các dãy nhị phân có độ dài ~n~, mỗi dãy cách nhau một dấu cách (theo thứ tự từ điển). Dòng cuối ghi tổng số dãy nhị phân.

Sample Input 1

3

Sample Output 1

000 001 010 011 100 101 110 111
8