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à khu ~3~, nhưng không được vào khu ~2~ và khu ~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.

Dữ liệu đầu vào

Gồm số nguyên dương ~n~ ~(2 \le n \le 17)~.

Dữ liệu đầu ra

Gồm hai dòng:

• Dòng thứ nhất gồm 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 thứ hai ghi tổng số dãy nhị phân.

Ví dụ

Ví dụ 1

INPUT

3

OUTPUT

000 001 010 011 100 101 110 111
8