culori3

Culori3

Pasiunea Mirunei este să coloreze. Vacanţa trecută şi-a petrecut-o la bunica ei la ţară şi pentru că se cam plictisea s-a gândit să vopsească gardul de la casa bunicii.

Gardul este compus din N scânduri dispuse una lângă alta. Miruna a găsit în garajul bunicii $5$ cutii de vopsea de culori diferite: **albă, albastră, roşie, verde** şi **galbenă**. Când a vopsit gardul, Miruna a respectat următoarele reguli:

Gardul este compus din $N$ scânduri dispuse una lângă alta. Miruna a găsit în garajul bunicii $5$ cutii de vopsea de culori diferite: $albă, albastră, roşie, verde$ şi $galbenă$. Când a vopsit gardul, Miruna a respectat următoarele reguli:

-	Dacă o scândură era vopsită cu **alb**, următoarea scândură o vopsea obligatoriu cu **albastru**
 
-	Dacă o scândură era vopsită cu **albastru**, atunci următoarea scândură o vopsea cu **alb** sau **roşu**
 
-	Dacă o scândură era vopsită cu **roşu**, atunci următoarea scândură o vopsea cu  {**albastru**} sau **verde**
 
-	Dacă o scândură era vopsită cu **verde**, atunci următoarea scândură o vopsea cu  {**roşu**} sau **galben**
 
-	Dacă o scândură era vopsită cu **galben**, atunci următoarea scândură o vopsea obligatoriu cu **verde**

* Dacă o scândură era vopsită cu $alb$, următoarea scândură o vopsea obligatoriu cu $albastru$
* Dacă o scândură era vopsită cu $albastru$, atunci următoarea scândură o vopsea cu $alb$ sau $roşu$
* Dacă o scândură era vopsită cu $roşu$, atunci următoarea scândură o vopsea cu $albastru$ sau $verde$
* Dacă o scândură era vopsită cu $verde$, atunci următoarea scândură o vopsea cu $roşu$ sau $galben$
* Dacă o scândură era vopsită cu $galben$, atunci următoarea scândură o vopsea obligatoriu cu $verde$

După ce a şi-a terminat treaba Miruna îşi admira “opera de artă” şi se întreba în câte moduri diferite ar fi putut să vopsească gardul bunicii.

h2. Cerinţă
 
Ajutaţi-o pe Miruna să găsească răspunsul la întrebarea sa.

h2. Date de intrare

Fişierul de intrare $culori3.in$ ...

Fişierul de intrare $culori3.in$ conţine pe prima sa linie un singur număr natural $N$.

h2. Date de ieşire

În fişierul de ieşire $culori3.out$ ...

Fişierul de ieşire $culori3.out$ va conţine pe prima sa linie un singur număr întreg reprezentând numărul de moduri diferite în care Miruna ar fi putut să vopsească gardul bunicii..

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 5000$
* Pentru $25%$ dintre teste $N ≤ 45$

h2. Exemplu

table(example). |_. culori3.in |_. culori3.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

table(example). |_. culori3.in |_. culori3.out |_. Explicaţie |
| $4$
| $24$
| Gardul poate fi vopsit astfel:
(alb,albastru,alb,albastru); (alb,albastru,rosu,albastru);
(alb,albastru,rosu,verde); (albastru,alb,albastru,alb);
(albastru,alb,albastru,rosu); (albastru,rosu,albastru,alb);
(albastru,rosu,albastru,rosu); (albastru,rosu,verde,rosu);
(albastru,rosu,verde,galben); (rosu,albastru,alb,albastru);
(rosu,albastru,rosu,albastru); (rosu,albastru,rosu,verde);
(rosu,verde,rosu,albastru); (rosu,verde,rosu,verde);
(rosu,verde,galben,verde); (verde,rosu,albastru,alb);
(verde,rosu,albastru,rosu); (verde,rosu,verde,rosu);
(verde,rosu,verde,galben); (verde,galben,verde,rosu);
(verde,galben,verde,galben); (galben,verde,rosu,albastru);
(galben,verde,rosu,verde); (galben,verde,galben,verde); |

...
== include(page="template/taskfooter" task_id="culori3") ==
 

== include(page="template/taskfooter" task_id="culori3") ==

7681