Coloration

Johnny a găsit acum câteva zile un joc străvechi în podul bunicului său din Nostilcio. Jocul se numește Coloration și constă dintr-o tablă de lungime $N$ și lățime $1$. Scopul jocului este să colorezi toată tabla folosind paleta cu $N$ culori găsită lângă tabla de joc, respectând următoarele reguli:

• Tabla este delimitată în $N$ celule, fiecare de dimensiune $1 \times 1$, notate de la stânga la dreapta cu numere de la $1$ la $N$.
• Culorile sunt notate cu numere de la $1$ la $N$.
• Tabla trebuie colorată complet.
• Culoarea $i$ poate acoperi o singură porțiune continuă de celule $(l, r)$, cu condiția ca $l \leq i \leq r$, sau poate să nu fie folosită deloc.

Cerință

Mama lui Johnny îi dă o nouă sarcină băiatului, dar el e prea preocupat să se joace Liga Legendelor, așa că vă cere ajutorul vostru: "În câte moduri poate colora Johnny tabla?". Deoarece rezultatul poate fi foarte mare, Mama lui Johnny se mulțumește cu acesta modulo $10^9 + 7$.

Date de intrare

Pe prima linie a fișierului de intrare coloration.in se găsește un singur număr întreg $N$, reprezentând lungimea tablei.

Date de ieșire

Pe prima linie a fișierului de ieșire coloration.out se va găsi un singur număr întreg, numărul de moduri de colorare a tablei modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$;

Exemplul 1

coloration.in

2

coloration.out

3

Explicație

Sunt $3$ moduri de a colora complet tabla cu $N = 2$ celule:

Varianta 1	Varianta 2	Varianta 3

Exemplul 2

coloration.in

149

coloration.out

395488370