| Fişierul intrare/ieşire: | kangaroo.in, kangaroo.out | Sursă | CEOI 2016, Ziua 1 |
| Autor | Adrian Panaete, Pit-Rada Vasile | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Kangaroo
O grădină este compusă dintr-o linie cu N celule numerotate de la 1 la N. Iniţial toate celulele conţin plante. Un cangur porneşte din celula numerotată cs Apoi el sare din celulă în celulă, mâncând plantele pe care le întâlneşte. Întotdeauna se opreşte în celula numerotată cf după ce vizitează fiecare dintre cele N celule exact o dată, inclusiv cs şi cf. Evident, cangurul va face N-1 sărituri.
Cangurul nu vrea să fie prins şi de aceea după fiecare săritură el îşi schimbă direcţia în care sare mai departe: dacă el se află în celula numerotată current, imediat după ce a sărit aici din celula numerotată prev şi va sări din celula numerotată current în celula numerotată next, atunci:
- daca prev < current, atunci next < current; altfel,
- daca current < prev, atunci current < next.
Cunoscând numărul N al celulelor din grădină, celula iniţială cs de unde cangurul porneşte să mănânce plante şi celula finală cf în care cangurul se opreşte, trebuie să calculaţi numărul de rute distincte pe care cangurul le poate face în timp ce sare prin grădină.
Date de intrare
Fişierul de intrare kangaroo.in va conţine trei numere întregi pozitive N, cs, cf, separate prin câte un spaţiu.
Date de ieşire
În fişierul de ieşire kangaroo.out trebuie să scrieţi un singur număr întreg ce reprezintă numărul de rute distincte pe care cangurul le poate face modulo 1000000007 (109 + 7).
Restricţii
- 2 ≤ N ≤ 2000
- 1 ≤ cs ≤ N
- 1 ≤ cf ≤ N
- cf ≠ cf
- Pentru teste în valoare de 6 puncte, N ≤ 8.
- Pentru teste în valoare de 36 puncte, N ≤ 40.
- Pentru teste în valoare de 51 puncte, N ≤ 200.
- Orice rută este unic determinată de ordinea în care se vizitează celulele.
- Se garantează pentru fiecare test că există cel puţin o rută care respectă regulile.
- Cangurul poate să sară în orice direcţie din cs.
Exemplu
| kangaroo.in | kangaroo.out |
|---|---|
| 4 2 3 | 2 |
Explicaţie
Cangurul porneşte din celula 2 şi se opreşte în celula 3. Cele două rute corecte sunt 2 -> 1 -> 4 -> 3 şi 2 -> 4 -> 1 -> 3.
