flori

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.

Cerinţă

Fiind dat $n$, numărul de flori, să se determine în câte moduri se poate forma buchetul.

Date de intrare

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

Date de ieşire

Fişierul de ieşire flori.out conţine pe prima linie un număr natural ce reprezintă numărul de buchete $mod \ 9 \ 001$.

Restricţii şi precizări

• $1 \leq n \leq 10 \ 000$
• 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 $1 \ 000$

Exemplul 1

flori.in

5

flori.out

12

Explicație

Se pot forma: $\{ 1 \}, \{ 2 \}, \{ 3 \}, \{ 4 \}, \{ 5 \}, \{ 1, 3 \}, \{ 1,4 \}, \{ 1,5 \}, \{ 1, 3, 5 \}, \{ 2, 4 \}, \{ 2, 5 \}, \{ 3, 5 \}$

Exemplul 2

flori.in

7

flori.out

33

Explicație

Se pot forma : $\{ 1 \}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{7\}, \{1, 3\}, \{1,4\}, \{1,5\}, \{1,6\}, \{1,7\},\{1,3,5\}, \{1,3,6\}, \{1,3,7\},$

$\{1,4,6\}, \{1,4,7\},\{1,5,7\}, \{1,3,5,7\}, \{2, 4\}, \{2, 5\}, \{2,6\},\{2,7\},$

$\{2,4,6\}, \{2,4,7\}, \{2,5,7\}, \{3, 5\}, \{3,6\},\{3,7\}, \{3,5,7\}, \{4,6\},\{4,7\}, \{5,7\}$