Mỗi thẻ từ được gắn với một mã nhị phân độ dài ~n~. Mỗi bit thể hiện quyền truy cập vào một khu vực: 1 là có quyền, 0 là không có quyền.

Yêu cầu

Liệt kê tất cả các dãy nhị phân độ dài ~n~ theo thứ tự từ điển và in tổng số dãy.

Input

Một số nguyên dương ~n~ ~(2 \le n \le 17)~.

Output

In tất cả các dãy nhị phân độ dài ~n~, mỗi dãy cách nhau một dấu cách. Dòng cuối in tổng số dãy nhị phân.

Subtask

• Một subtask duy nhất với ~2 \le n \le 17~.

Ví dụ

3

000 001 010 011 100 101 110 111
8