第 3 题 Piratski kod (`piratskikod`)

时间限制 1.0 s · 空间限制 256 MB · 3 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 piratskikod.in，输出文件 piratskikod.out。

译自 COCI 2023/2024 Contest #5 T3 [Piratski kod]

题目描述

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

信息如下：

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

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

这里的 $\mathrm{Fib}[x]$ 表示第 $x$ 个斐波那契数。斐波那契数的定义如下： $\mathrm{Fib}[1] = 1$ ， $\mathrm{Fib}[2] = 1$ ，对于每个 $y > 2$ ， $\mathrm{Fib}[y] = \mathrm{Fib}[y-1] + \mathrm{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$ 的密码谜题的答案。

样例

样例 1

输入：

输出：

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 = 5\,000$

第 3 题 Piratski kod (piratskikod)