Puzzle horitzontal P74317

Statement

Disposeu d’una col·lecció infinita de peces $1 \times 1$ , $1 \times 2$ i $2 \times 2$ , i heu d’omplir totalment un rectangle $2 \times n$ . De quantes maneres ho podeu fer?

Per exemple, aquesta és una de les moltes maneres per a $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

Entrada

L’entrada consisteix en diversos casos, cadascun amb una $n$ entre 1 i $10^4$ .

Sortida

Per a cada cas, escriviu el nombre de maneres d’omplir un rectangle $2 \times n$ . Com que aquest nombre pot ser molt gros, feu els càlculs mòdul $10^8 + 7$ .

Observació

Potser us pot ser útil calcular també una quantitat semblant a la que demana el problema.

Public test cases

Input

Output

Information

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