Limbaj formal

Enunț

RAU-Gigel se pregătește pentru admiterea la facultate. Curios din fire, el împrumută niște cursuri de la un prieten student, de unde află despre limbajele formale, gramatici, automate finite, expresii regulate și multe alte lucruri interesante. Găsește acolo și o problemă: Se consideră un alfabet $X$ format din $N$ simboluri (diferite două câte două). Pe mulțimea $X$ este definită o relație de ordine totală (să o numim lexicografică), adică orice două elemente $a$ și $b$ alegem din $X$ ($a$ diferit de $b$), avem fie $a \lt b$, fie $b \lt a$. Câte cuvinte se pot forma cu simboluri din alfabetul $X$ astfel încât simbolurile prezente în cuvânt să fie în ordine strict crescătoare (de la stânga spre dreapta) și să nu existe în cuvânt două simboluri consecutive lexicografic? Deoarece calculele devin destul de complicate, RAU-Gigel ar avea nevoie de ajutorul vostru. În plus, numerele obținute s-ar putea să fie destul de mari, RAU-Gigel ar vrea să le calculați modulo ${MOD}$.

Cerința

Ajutați-l pe RAU-Gigel să afle răspunsul la întrebare. Repede, dacă puteți!

Date de intrare

Fișierul de intrare limbajformal.in conține pe prima linie un număr natural $N$ reprezentând numărul de simboluri din alfabet.

Date de ieșire

Fișierul de ieșire limbajformal.out va conține un singur rând, pe care se află un sigur număr reprezentând răspunsul la întrebare.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000 \ 000, MOD = 1 \ 000 \ 000 \ 009$;
• Cuvintele au cel puțin un simbol;
• Pentru teste în valoare de $10$ de puncte: $N \leq 10$;
• Pentru teste în valoare încă $30$ de puncte: $N ≤ 1 \ 000 \ 000$.

Exemplu

limbajformal.in

5

limbajformal.out

12

Explicație:

Alfabetul conține $5$ simboluri. Să le notăm $A, B, C, D, E$, cu $A < B < C < D < E$. Există $12$ cuvinte care respectă cerințele problemei: $A, B, C, D, E, AC, AD, AE, BD, BE, CE, ACE$. Secvența $AB$ nu este validă pentru că simbolurile $A$ și $B$ sunt consecutive lexicografic. Secvența $ADE$ nu este validă pentru că simbolurile $D$ și $E$ sunt consecutive lexicografic.