Studiu

Time limit: 0.4s Memory limit: 64MB Input: studiu.in Output: studiu.out

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 NN persoane și le-a implicat într-un test care decurge astfel:

  • Sunt NN locuri pe un rând.
  • Sunt NN persoane numerotate de la 11 la NN.
  • Cele NN 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 11;
    • a treia persoană (dacă există) alege locul cel mai îndepărtat de 11 și de 22;
    • 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 NN persoane, conform regulilor din enunț.

Date de intrare

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

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 NN persoane. Deoarece această valoare poate fi foarte mare, să se afișeze rezultatul modulo 1 000 000 0071\ 000\ 000\ 007.

Restricții și precizări

  • 1N100 000 0001 \leq N \leq 100\ 000\ 000
  • Două șiruri de NN persoane AA și BB sunt considerate diferite dacă pe o poziție ii diferă numerele asociate persoanelor respective în cele două șiruri (AiBiA_i \neq B_i).
# Punctaj Restricții
1 13 1N100 0001 \leq N \leq 100\ 000 și NN impar
2 13 1N100 0001 \leq N \leq 100\ 000 și NN par
3 18 100 001N10 000 000100\ 001 \leq N \leq 10\ 000\ 000 și NN impar
4 18 100 001N10 000 000100\ 001 \leq N \leq 10\ 000\ 000 și NN par
5 38 Fără restricții suplimentare

Exemplul 1

studiu.in

3

studiu.out

2

Explicație

N=3N = 3: 213|2|1|3|, 312|3|1|2|

Exemplul 2

studiu.in

5

studiu.out

4

Explicație

N=5N = 5: 24153|2|4|1|5|3|, 25143|2|5|1|4|3|, 34152|3|4|1|5|2|, 35142|3|5|1|4|2|

Log in or sign up to be able to send submissions!