[COCI 2023/2024 #5] 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 无法打开宝箱，她的船员将认为她不值得信任，并将她逼上走板。 ## Input 一行一个整数 $n\ (n\le 5\ 000)$。 ## Output 输出一行 $n$ 个整数，其中第 $k$ 个整数表示长度为 $k$ 的密码谜题的答案。 [samples] ## Background **译自 [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T3「[Piratski kod](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」** ## Note ### 样例解释 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$ |