Siruri 2-3-monotone

sir23

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

== include(page="template/taskheader" task_id="sir23") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| sir23.in | sir23.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== 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")==