Horizontal puzzle P74317

Statement

Have an infinite collection of pieces $1 \times 1$ , $1 \times 2$ and $2 \times 2$ , and you must completely fill a $2 \times n$ rectangle. In how many ways can you do it?

For example, this is one of the many ways for $n = 7$ :

(9,4)

(1,1)(1,0)7 (1,1)(0,1)2 (8,3)(-1,0)7 (8,3)(0,-1)2

(2,1)(0,1)2 (2,2)(1,0)1 (3,1)(0,1)1 (3,2)(1,0)1 (4,2)(0,1)1 (4,2)(1,0)1 (5,1)(0,1)2 (7,1)(0,1)2 (7,2)(1,0)1

Input

Input consists of several cases, each with an $n$ between 1 and $10^4$ .

Output

For every case, print the number of ways to fill a $2 \times n$ rectangle. Since this number can be very large, make the computations modulo $10^8 + 7$ .

Observation

It may be helpful to compute a quantity similar to the one asked for in the problem.

Public test cases

Input

Output

Information

Author: Salvador Roura
Language: English
Translator: Salvador Roura
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++ Java