flori4

Flori 4

== include(page="template/taskheader" task_id="flori4") ==

Poveste şi cerinţă...

Lalelele din Parcul Soarelui au fost numerotate de la $1$ la $n$. Se doreşte formarea unui buchet, care să conţină cel puţin o floare, iar două flori numerotate consecutiv să nu aparţină buchetului.
 
h2. Cerinţă
 
Fiind dat $n$, numărul de flori, să se determine în câte moduri se poate forma buchetul.

h2. Date de intrare

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

Fişierul de intrare $flori4.in$ conţine pe prima linie un număr natural $n$, reprezentând numărul de flori.

h2. Date de ieşire

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

În fişierul de ieşire $flori4.out$ conţine pe prima linie un număr natural ce reprezintă numărul de buchete modulo &9001&.

h2. Restricţii

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

* &1 ≤ n ≤ 10000;&
* Pentru $30%$ din teste $n$ este mai mic sau egal decât $26$;
* Pentru $60%$ din teste $n$ este mai mic sau egal decât $1000$.

h2. Exemplu

...

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

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