2 by n Tiling 2

Interview

Time limit1sMemory limit256 MB

Summary

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

Level: Easy3 of 10
Topics: Dynamic programming
Solved: No attempts yet

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.

Examples3

Example 1
Input
```
2
```
Expected output
```
3
```
Example 2
Input
```
8
```
Expected output
```
171
```
Example 3
Input
```
12
```
Expected output
```
2731
```