==Include(page="template/taskheader" task_id="sir23")==

==Include(page="template/taskheader" task_id="sir23")==
 
Fie $N$ ({$N$} ≤ $1000$) un numar natural. Numim sir _2-3-monoton_ de lungine $N$ un sir $S{~1~}$, $S{~2~}$, $S{~3~}$, ... $S{~n~}$ format din $N$ elemente ale multimii ${1, 2, ... N}$ care verifica urmatoarele doua relatii:
 
* $S{~i~}$ < $S{~i+2~}$, oricare ar fi $1$ ≤ $i$ ≤ $N-2$
* $S{~i~}$ < $S{~i+3~}$, oricare ar fi $1$ ≤ $i$ ≤ $N-3$
 
h2. Cerinta
 
Fie $X$ numarul de siruri _2-3-monotone_ de lungime $N$. Calculati restul impartirii lui $X$ la $1.000.000$ (1 milion).
 
h2. Date de intrare
 
Fisierul $sir23.in$ va contine pe prima linie numarul intreg $N$.
 
h2. Date de iesire
 
Pe prima linie a fisierului $sir23.out$ se va scrie numarul cautat.
 
h2. Exemple
 
table(example). |_. sir23.in |_. sir23.out |
| 2 | 4 |
| 3 | 9 |
| 5 | 88|
 
==Include(page="template/taskfooter" task_id="sir23")==

==Include(page="template/raw")==
Siruri 2-3-monotone
(enunt adaptat)
Fie N (N<=1000) un numar natural. Numim sir 2-3-monoton de lungine N un sir S[1], S[2], S[3], ... S[n] format din n elemente ale multimii {1, 2, ... n} care verifica urmatoarele doua relatii:
 
* S[i] < S[i+2], oricare ar fi 1<=i<=n-2
* S[i] < S[i+3], oricare ar fi 1<=i<=n-3
 
h2. Cerinta
 
Fie X numarul de siruri 2-3-monotone de lungime N. Calculati restul impartirii lui X la 1000000 (1 milion).
 
h2. Date de Intrare
 
Fisierul sir23.in va contine pe prima linie numarul intreg N.
 
h2. Date de Iesire
 
Pe prima linie a fisierului sir23.out se va scrie numarul cautat.
 
 
 
Exemple
 
sir23.in
 
2
 
sir23.out
 
4
 
sir23.in
 
3
 
sir23.out
 
9
 
sir23.in
 
5
 
sir23.out
 
88
==Include(page="template/taskfooter" task_id="sir23")==

45