Horizontal puzzle P74317


Statement
 

pdf   zip

html

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

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

unit=1.2cm (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 104.

Output

For every case, print the number of ways to fill a 2 × n rectangle. Since this number can be very large, make the computations modulo 108 + 7.

Observation

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

Public test cases

  • Input

    1
2
3
4
10000

    Output

    2
8
26
90
52273134
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Java