Mã hóa thẻ

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ị phân để 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.

Example

Input:

3

Output:

000 001 010 011 100 101 110 111
8