Algorithmes et Structures de Données

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

Entrée
Sortie
1
2
2
2
3
4

Explication

  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