Totxanes P88430


Statement
 

pdf   zip

Disposeu d’un nombre il·limitat de totxanes 3×13 \times 1. Podeu posar cada totxana verticalment o horitzontalment. De quantes maneres podeu cobrir un rectangle n×3n \times 3? Les totxanes no poden solapar-se ni sortir del rectangle.

Per exemple, per a n=4n=4 hi ha tres maneres (mireu el pdf de l’enunciat per veure-ho bé):

(34,8) (1,1)(3,7) (3,1)(5,7) (5,1)(7,7) (7,1)(9,7) (1,1)(1,7) (3,1)(3,7) (5,1)(5,7) (7,1)(7,7) (9,1)(9,7) (1,1)(9,1) (1,3)(9,3) (1,5)(9,5) (1,7)(9,7) (13,1)(19,3) (13,3)(19,5) (13,5)(19,7) (19,1)(21,7) (13,1)(13,7) (15,1)(15,7) (17,1)(17,7) (19,1)(19,7) (21,1)(21,7) (13,1)(21,1) (13,3)(21,3) (13,5)(21,5) (13,7)(21,7) (27,1)(33,3) (27,3)(33,5) (27,5)(33,7) (25,1)(27,7) (25,1)(25,7) (27,1)(27,7) (29,1)(29,7) (31,1)(31,7) (33,1)(33,7) (25,1)(33,1) (25,3)(33,3) (25,5)(33,5) (25,7)(33,7)

Entrada

L’entrada consisteix en diverses nn entre 1 i 10510^5.

Sortida

Per a cada nn donada, escriviu una línia amb el resultat. Com que el resultat pot ser molt gran, (per exemple, per a n=50n=50 ja seria 122106097), per evitar sobreiximents feu tots els càlculs mòdul 100000007 (108+710^8 + 7).

Pista

Si repetiu càlculs la vostra solució pot ser massa lenta.

Public test cases

  • Input

    1
3
4
10
49
50
60
100000
60

    Output

    1
2
3
28
83316385
22106090
82215970
77894047
82215970
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++