Peindre avec des couleurs

Vous souhaitez peindre une bande en utilisant 3 couleurs : red, blue et orange. Vous peignez chaque unité avec une seule couleur. Pour la rendre plus attrayante, vous avez décidé de suivre ces règles :

1. Vous ne pouvez pas placer la même couleur côte à côte.

2. La couleur blue doit toujours être placée entre la red et la orange ou entre la orange et la red.

Combien de bandes différentes peut-on obtenir s’il y a n unités dans la bande ?

Entrée

L’entrée contient un seul entier n (1 ≤ n ≤ ).

Sortie

Le programme doit afficher le nombre de bandes différentes que vous pouvez obtenir. Comme la réponse peut être très grande, il faut l’afficher modulo .

Exemples

Explication

1. (red) (orange)

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

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