해적 코드

선장 마르트리나와 해적 선원들은 이탈리아에서 가장 유명한 해적이 남긴 오래된 보물을 3개월 동안 찾아다닌 끝에, 금화가 가득 든 상자를 마침내 파냈다. 상자를 열려면 비밀 조합이 필요하다. 그 조합은 상자 옆에 있던 병 속 편지에 적혀 있다.

편지에는 다음과 같이 적혀 있다:

가장 가치 있는 해적만 상자를 열 수 있도록, 조합은 다음 문제의 답이다. 길이가 $a$인 이진 수열 $s$에서 연속한 1의 쌍이 수열의 끝에만 있을 때, 이 수열을 수 $x$의 해적 표현이라 한다. 그 조건은 다음과 같다.

$\sum_{i=0}^{a-2} s[i] \cdot Fib[2+i] = x$

여기서 $Fib[x]$는 $x$번째 피보나치 수이다. 피보나치 수는 $Fib[1] = 1$, $Fib[2] = 1$이고, $y > 2$인 모든 $y$에 대해 $Fib[y] = Fib[y-1] + 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

첫 번째이자 유일한 줄에 양의 정수 $n$이 주어진다. ($n \le 5000$)

한 줄에 $n$개의 수를 출력한다. $k$번째 수는 길이가 $k$인 코드 문제의 답이다.

길이가 $1$인 코드는 $0$과 $1$이며, 둘 다 값이 $0$이다.

코드 $11$의 값은 $1$이고, 길이가 $1$인 나머지 코드의 값은 모두 $0$이다.

코드 $1111$의 값은 $2$이고, 코드 $0011$의 값은 $3$이다.