Thuyền trưởng Marrrtina, cùng với băng cướp biển của mình, sau ba tháng tìm kiếm kho báu thất lạc từ lâu của tên cướp biển nổi tiếng nhất nước Ý, cuối cùng đã đào được chiếc rương chứa đầy kho báu. Nhưng để mở khóa chiếc rương, cô ấy cần một sự kết hợp bí mật được mô tả trong lời nhắn đặt trong chiếc chai bên cạnh chiếc rương.

Lời nhắn nói rằng:

Để tên cướp biển xứng đáng nhất mới có thể mở được chiếc rương, sự kết hợp là lời giải cho câu đố sau: Một dãy nhị phân s có độ dài ~a~ trong đó cặp số liên tiếp duy nhất nằm ở cuối chuỗi là biểu diễn hệ cướp biển của một số ~x~ nếu

$$s[0].Fib[2] + s[1].Fib[3] + ... + s[a-2].Fib[a] = x.$$

trong đó ~Fib[x]~ là số Fibonacci thứ ~x~.

Ví dụ, ~11_p = 1, 011+p = 2, 1010011_p = 17~, trong đó ~_p~ thể hiện biểu diễn hệ cướp biển của số.

Một mã cướp biển là một dãy nhị phân (không có điều kiện về hai số ~1~ liên tiếp) biểu diễn một số nguyên dương. Để đọc nó, chúng ta phân chia nó thành càng nhiều phần càng tốt để là biểu diễn hệ cướp biển của một số nào đó (và có thể hậu tố không phải là biểu diễn hệ cướp biển của bất kỳ số nào) và viết các số nguyên đó theo một chuỗi. Ví dụ: chúng ta phân chia ~01111010110101~ thành ~011|11|01011|0101~, phần cuối cùng không phải là biểu diễn hệ cướp biển nên ta xóa nó ~011|11|01011~ và đọc chuỗi ~2, 1, 7~.

Giá trị của mã cướp biển bằng tổng các giá trị của chuỗi số nguyên dương được giải mã. Giá trị của mã trên là ~10~.

Số ~P~ yêu thích của tôi là tổng giá trị của tất cả các mã cướp biển có độ dài ~k~. Vì con số đó có thể lớn nên sự kết hợp của rương là phần dư của ~P~ khi chia cho ~10^9+7~.

Nếu Marrrtina không mở được chiếc rương, thủy thủ đoàn của cô ấy sẽ không coi cô ấy ra gì và họ sẽ bắt cô ấy đi trên ván.

Input

Nhập một dòng duy nhất gồm một số nguyên dương ~n \leq 5 \times 10^3~.

Output

Đưa ra một dòng gồm ~n~ số mà số thứ ~k~ là tổng giá trị của các mã cướp biển độ dài ~k~.

Scoring

1. ~n = 20~ (20 điểm)

2. ~n = 300~ (40 điểm)

3. ~n = 5 \times 10^3~ (50 điểm)

Sample Input

4

Sample Output

0 1 4 16