题目背景

译自 COCI 2023/2024 Contest #5 T3「Piratski kod」

题目描述

Marrrtina 船长和她的海盗团队，在搜索了三个月之后，终于挖掘出一箱属于最著名的意大利海盗的失落宝藏。但是，要打开这个宝箱，她需要一个密码，该密码被描述在宝箱旁边的一个瓶子中的一条信息中。

信息如下：

---

只有最有价值的海盗才能打开宝箱，密码是以下谜题的答案：对于长度为 $a$ 的二进制序列 $s$，且其中唯一的连续两个 $1$ 位于序列的末尾，如果满足以下条件，它是一个数字 $x$​ 的海盗表示：

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

这里的 $\text{Fib}[x]$ 表示第 $x$ 个斐波那契数。斐波那契数的定义如下：$\text{Fib}[1] = 1$，$\text{Fib}[2] = 1$，对于每个 $y > 2$，$\text{Fib}[y] = \text{Fib}[y − 1] + \text{Fib}[y − 2]$。

例如，$11_p = 1$，$011_p = 2$，$1010011_p = 17$，这里的 $p$ 表示数字的海盗表示。

海盗代码是一个二进制序列（没有关于连续 $1$ 的任何条件），代表一系列正整数的序列。为了阅读它，我们将其分割为尽可能多的部分，这些部分是某些数字的海盗表示（可能还有一个不是任何数字的海盗表示的后缀），并按顺序写出这些整数。例如，我们将 $01111010110101$ 分割为 $011|11|01011|0101$，最后一部分不是海盗表示，因此我们删除它，得到 $011|11|01011$，并读到序列 $2,1,7$。

海盗代码的值等于解码后的正整数序列的值之和。前面的密码的值为 $10$。

我最喜欢的数字 $P$ 是长度为 $k$ 的所有海盗代码值的总和。由于该数字可能很大，打开宝箱的密码是 $P$ 除以 $10^9 + 7$ 的余数。

— Leonarrrdo da Pisa

---

如果 Marrrtina 无法打开宝箱，她的船员将认为她不值得信任，并将她逼上走板。

输入格式

一行一个整数 $n\ (n\le 5\ 000)$。

输出格式

输出一行 $n$ 个整数，其中第 $k$ 个整数表示长度为 $k$ 的密码谜题的答案。

4

0 1 4 16

提示

样例解释 1

长度为 $1$ 的代码是 $0$ 和 $1$，它们的值都是 $0$。

代码 $11$ 的值为 $1$，其余所有长度为 $2$ 的代码值都是 $0$。

代码 $1111$ 的值为 $2$，$0011$ 的值为 $3$。

子任务

Subtask	Points	Constraints
1	20	$n=20$
2	40	$n=300$
3	50	$n=5000$