Algoritmi e Strutture Dati

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.
  1. 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

Ingresso
Uscita
1
2
2
2
3
4

Spiegazione

  1. (red) (orange)
  1. (red, orange) (orange, red)
  1. (orange, red, orange) (red, blue, orange) (orange, blue, red) (red, orange, red)
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue