Thuyền trưởng Hạo, 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 của tên cướp biển Ý nổi tiếng nhất, cuối cùng đã đào được rương đầy kho báu. Nhưng để mở khóa rương, anh cần một mật mã được mô tả trong một bức thư trong chai bên cạnh rương.

Bức thư viết:

• Để chỉ có cướp biển xứng đáng nhất mới có thể mở rương, mật mã 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ố \(1\) liên tiếp duy nhất nằm ở cuối dãy là biểu diễn cướp biển của số \(x\) nếu:

\[s[0] \cdot Fib[2] + s[1] \cdot Fib[3] + s[2] \cdot Fib[4] + \ldots + s[a-2] \cdot Fib[a] = \sum_{i=0}^{a-2} s[i] \cdot Fib[2+i] = x\]

• Trong đó Fib[x] là số Fibonacci thứ \(x\). Số Fibonacci được định nghĩa: \(Fib[1] = 1, Fib[2] = 1, Fib[y] = Fib[y-1] + Fib[y-2]\) với mọi \(y > 2\).

Ví dụ: \(11_p = 1, 011_p = 2, 1010011_p = 17\), trong đó \(p\) biểu thị biểu diễn cướp biển của một số.

Mã cướp biển là một dãy nhị phân (không có điều kiện về các số 1 liên tiếp) biểu diễn một dãy các 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 cướp biển của một số nào đó (và có thể có một hậu tố không phải là biểu diễn cướp biển của bất kỳ số nào) và viết các số nguyên đó thành một dãy. 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 cướp biển nên chúng ta xóa nó 011|11|01011 và đọc được dãy \(2, 1, 7\).

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

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

Nếu Hạo không thể mở rương, băng cướp biển sẽ không coi anh là xứng đáng và họ sẽ bắt anh phải đi trên ván gỗ.

Đầu vào

• Dòng đầu tiên và duy nhất chứa một số nguyên dương \(n \le 5000\).

Đầu ra

• Trên một dòng duy nhất, in ra \(n\) số trong đó số thứ \(k\) biểu thị đáp án cho câu đố với các mã có độ dài \(k\).

Chấm điểm

Input 1

4

Output 1

0 1 4 16

Làm rõ: Các mã có độ dài 1 là 0 và 1 và cả hai đều có giá trị 0. Mã 11 có giá trị 1 trong khi tất cả các mã khác có độ dài 1 có giá trị 0. Mã 1111 có giá trị 2, và mã 0011 có giá trị 3.