Pirate Code Treasure

Captain Marrrtina and her pirate crew have discovered the long‐lost treasure of the most famous Italian pirate. To open the treasure chest, she must enter a secret password hidden in a mysterious bottle. The bottle contains the following riddle:

Only the most valuable pirates can open the chest – the password is the answer to the following puzzle: Consider a binary sequence s of length \(a\) with the property that the only occurrence of two consecutive 1’s appears at the very end (i.e. \(s[a-2]=s[a-1]=1\) and for every \(0 \le i \le a-3\), \((s[i],s[i+1])\ne(1,1)\)). Such a sequence is called a pirate representation of the positive integer \(x\) if

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

where \(Fib(1)=1,\; Fib(2)=1,\) and for every \(y>2\), \(Fib(y)=Fib(y-1)+Fib(y-2)\). For example,

• 11p represents \(1\);
• 011p represents \(2\);
• 1010011p represents \(17\).

A pirate code is any binary sequence (with no restrictions on consecutive 1’s) that encodes a sequence of positive integers as follows. We split the pirate code into as many parts as possible such that each part is some pirate representation of a number (if a suffix does not form a pirate representation, it is ignored), and then we read the positive integers in order. For example, the code

01111010110101

can be split as 011 | 11 | 01011 | 0101; the last part is not a valid pirate representation and is discarded. Thus the decoded sequence is \(2, 1, 7\) and the overall pirate code value is \(2+1+7=10\).

Let \(P\) be the sum of the pirate code values over all binary sequences of length \(k\). Since \(P\) may be very large, the password is \(P \bmod (10^9+7)\). Your task is to compute this residue.

If Captain Marrrtina fails to open the chest, her crew will no longer trust her. Solve the puzzle and help her!

inputFormat

The input consists of a single integer \(k\) (\(1 \le k \le 2000\)), the length of the pirate code.

outputFormat

Output one integer, the value of \(P\) modulo \(10^9+7\).

Explanation: We consider all \(2^k\) binary sequences of length \(k\). For each sequence, we decode it by greedily splitting it into the maximum number of segments from left to right. A segment is a valid pirate representation if it has length \(a\ge2\), its last two digits are both 1, and no other two consecutive 1’s occur. The value of a segment \(s[0\ldots a-1]\) (written as \(s_p\)) is \(\sum_{i=0}^{a-2} s[i]\cdot Fib(i+2)\). The pirate code’s value is the sum of the decoded numbers. \(P\) is the total sum of the values for all binary sequences of length \(k\).

sample

2

1