2 by n Tiling

Interview

Time limit1sMemory limit256 MB

Summary

Count the ways to tile a 2 by n rectangle with 1 by 2 dominoes and print the count 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 by $n$ rectangle completely with 1 by 2 tiles and 2 by 1 tiles. Tiles may not overlap and may not stick out of the rectangle.

The picture below shows one way to fill a 2 by 5 rectangle.

Input

The first line contains $n$ . ( $1 \le n \le 1{,}000$ )

Output

Print the number of ways to fill the 2 by $n$ rectangle, modulo $10{,}007$ , on the first line.

Examples2

Example 1
Input
```
2
```
Expected output
```
2
```
Example 2
Input
```
9
```
Expected output
```
55
```