Dipingi con i colori

Vorresti dipingere una striscia con 3 colori: red, blue e orange. Ogni unità viene colorata con un singolo colore. Per renderla più vivace, hai deciso di rispettare le seguenti regole:

1. Non puoi posizionare due unità consecutive con lo stesso colore.

2. Il colore blue deve sempre trovarsi tra red e orange o tra orange e red.

Quante diverse strisce puoi ottenere se l’intera striscia è composta da n unità?

Ingresso

L’input contiene un singolo intero n (1 ≤ n ≤ ).

Uscita

Il programma deve stampare il numero di diverse strisce che è possibile ottenere. Poiché la risposta può essere molto grande, devi fornire il risultato modulo .

Esempi

Spiegazione

1. (red) (orange)

2. (red, orange) (orange, red)

3. (orange, red, orange) (red, blue, orange) (orange, blue, red) (red, orange, red)