Blocks for Kids

Wango is a brilliant maths teacher. He has two sons, Kango and Dango, born two years apart on the same day. Kango is 9 and Dango is 7. Their birthdays are approaching again. Wango wants to buy each son a piece of the Pango board to introduce them to higher mathematics.

A size $n$ ($n \ge 0$) Pango board is a $2 \times n$ rectangle of unit squares. A Pango board must be tiled completely with Pango pieces. Any tiling is acceptable. A size 0 board exists, is unique, and represents the empty set.

There are four types of Pango pieces. Each type can be used an unlimited number of times. Pieces cannot be rotated.

Wango buys one board of size $N$, chooses an integer $k$ ($0 \le k \le N$), and gives a size $k$ board to Kango and a size $N-k$ board to Dango. Both boards must be tiled completely. Count the number of ways Wango can give the presents. Two ways are distinct if Dango gets a different board or Kango gets a different board. Two boards are the same if they have the same tiling from left to right. Rotating a board is not allowed when comparing.

The input consists of several test cases, one per line. Each line contains one integer $N$ ($0 \le N \le 1000000000$), the size of the board Wango buys. The input ends with a line containing -1, which is not processed. There are at most 300 test cases.

For each test case, print one line with the number of ways Wango can distribute the presents, modulo 10007.