Studiu

Institutul Român de Psihologie a primit mult mai multe fonduri de la stat, după noi schimbări legislative. Un om de știință renumit dorește să facă un studiu asupra modului în care oamenii iau decizii în cadrul unui grup social din care nu fac parte. El a ales aleatoriu $N$ persoane și le-a implicat într-un test care decurge astfel:

• Sunt $N$ locuri pe un rând.
• Sunt $N$ persoane numerotate de la $1$ la $N$.
• Cele $N$ persoane vin una după alta pentru a ocupa locurile conform următoarelor reguli:
  • prima persoană se așează în mijlocul rândului;
  • a doua persoană (dacă există) alege locul cel mai îndepărtat de $1$;
  • a treia persoană (dacă există) alege locul cel mai îndepărtat de $1$ și de $2$;
  • fiecare persoană care urmează va alege un interval de lungime maximă de scaune neocupate și pe un astfel de interval va alege un scaun astfel încât distanța minimă până la orice scaun ocupat să fie maximă.

Cerință

Să se determine numărul de moduri în care pot fi așezate un număr de $N$ persoane, conform regulilor din enunț.

Date de intrare

Fișierul de intrare studiu.in conține pe prima linie numărul natural $N$.

Date de ieșire

Fișierul de ieșire studiu.out va conține pe prima linie numărul de moduri în care pot fi așezate cele $N$ persoane. Deoarece această valoare poate fi foarte mare, să se afișeze rezultatul modulo $1\ 000\ 000\ 007$.

Restricții și precizări

• $1 \leq N \leq 100\ 000\ 000$
• Două șiruri de $N$ persoane $A$ și $B$ sunt considerate diferite dacă pe o poziție $i$ diferă numerele asociate persoanelor respective în cele două șiruri ($A_i \neq B_i$).

Exemplul 1

studiu.in

3

studiu.out

2

Explicație

$N = 3$: $|2|1|3|$, $|3|1|2|$

Exemplul 2

studiu.in

5

studiu.out

4

Explicație

$N = 5$: $|2|4|1|5|3|$, $|2|5|1|4|3|$, $|3|4|1|5|2|$, $|3|5|1|4|2|$