Àngels i dimonis P20753


Statement
 

pdf   zip

thehtml

Hi ha n personatges en fila. Cadascun és un àngel o un dimoni. Quan parlen, els àngels sempre diuen la veritat, i els dimonis sempre menteixen. Excepte el primer personatge, que ara no diu res, cadascú afirma que el personatge de davant menteix quan parla.

Donada n, quantes distribucions possibles d’àngels i dimonis hi ha consistents amb el que afirmen els personatges? Per exemple, per a n = 1 només hi ha dues solucions: o bé el primer personatge és un àngel o bé és un dimoni.

Entrada

L’entrada consisteix en un natural n entre 1 i 105.

Sortida

Escriviu el nombre de solucions possibles mòdul 109 + 7.

Public test cases
  • Input

    1
    

    Output

    2
    
  • Information
    Author
    Max Balsells
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python