Àngels i dimonis P20753

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 10⁵.

Sortida

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