Tiling

A domino is a rectangular piece of size $2 \times 1$, and each of its two squares carries a number from 1 to 6. Dominoes are normally used to play a game, but here they are used for something else.

You can place dominoes without overlaps and without gaps to fill a rectangle of width $W$ and height 3. The goal is to count how many such fillings exist. The numbers printed on the pieces play no role, so two fillings count as different when the position or the orientation of at least one domino differs.

The figure below shows the three ways of filling a rectangle of width 2 and height 3.

A larger width admits many more fillings. For example, one possible answer for width 12 is this one.

Write a program that computes the number of ways to tile a rectangle of width $W$ and height 3 with dominoes.

The first line contains the width $W$ of the rectangle, with $1 \le W \le 1000$.

Print the number of fillings on the first line. The value can be very large, so print it modulo $1000000007$ ($10^9 + 7$).

For $W = 56$ the exact number of fillings is $8155103542731753$, and the value you print is that number modulo $10^9 + 7$.