À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^5$.

Sortida

Escriviu el nombre de solucions possibles mòdul $10^9$ + 7.