Marrrtina 船长和她的海盗船员在寻找属于最著名的意大利海盗的失落宝藏三个月后，终于挖出了一个装满财宝的箱子。但为了打开箱子，她需要一个写在箱子旁瓶中信里的秘密组合。
信上写道：
为了让只有最值得的海盗能够打开箱子，这个组合是以下谜题的解：一个长度为 $a$ 的二进制序列 $s$，其中唯一一对连续的 $1$ 位于序列末尾，它是数字 $x$ 的海盗表示，如果
$$s[0] \cdot \text{Fib}[2] + s[1] \cdot \text{Fib}[3] + s[2] \cdot \text{Fib}[4] + \dots + 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, \text{Fib}[y] = \text{Fib}[y-1] + \text{Fib}[y-2]$，对于每个 $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 \le 5000$。
输出格式
在单行中输出 $n$ 个数字，其中第 $k$ 个数字表示长度为 $k$ 的代码谜题的答案。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 20 | $n = 20$ |
| 2 | 40 | $n = 300$ |
| 3 | 50 | $n = 5000$ |
样例
输入 1
4
输出 1
0 1 4 16
说明
长度为 $1$ 的代码有 $0$ 和 $1$，它们的值均为 $0$。 代码 $11$ 的值为 $1$，而所有其他长度为 $2$ 的代码的值均为 $0$。 代码 $1111$ 的值为 $2$，代码 $0011$ 的值为 $3$。