2 by n Tiling 2

Count the ways to tile a 2 by n rectangle with dominoes and 2 by 2 squares, modulo 10007.

Easy3Dynamic programmingInterviewNo attempts yetTime limit1sMemory limit256 MB

Description

Examples3

Problem

Write a program that counts the ways to fill a $2 \times n$ rectangle with $1 \times 2$ , $2 \times 1$ , and $2 \times 2$ tiles. Tiles must not overlap, must not stick out of the rectangle, and must leave no empty cell.

Two fillings are different if any tile sits in a different place.

Input

The first line contains $n$ . ( $1 \le n \le 1000$ )

Output

Print the number of ways to fill the $2 \times n$ rectangle, modulo $10007$ , on the first line.