Collaret de perles (2) P89236

Volem fer un collaret amb perles blanques i negres, amb dues condicions:

• No hi poden haver quatre o més perles blanques adjacents.

• No hi poden haver dues o més perles negres adjacents.

Tingueu en compte que el collaret és circular, és a dir, la primera perla i l’última perla són adjacents. Per exemple, aquests són els sis collarets possibles amb quatre perles (una B indica una perla blanca, una N indica una perla negra):

(Els quatre primers collarets i els dos últims en el fons són iguals, però en aquest problema els distingirem.)

Quants collarets amb $n$ perles hi ha?

Entrada

L’entrada conté diversos casos, cadascun amb una $n$ entre 2 i $10^{12}$.

Sortida

Per a cada $n$, escriviu el nombre de collarets de perles de mida $n$. Com que el resultat pot ser molt gros, feu els càlculs mòdul $10^8 + 7$.

Puntuació

• Cas A:   Casos amb $n \le 15$, com l’exemple d’entrada 1.

• Cas B:   Casos amb $n \le 30$, com l’exemple d’entrada 2.

• Cas C:   Casos amb $n \le 10^5$, com l’exemple d’entrada 3.

• Cas D:   Casos de tot tipus, com l’exemple d’entrada 4