Fişierul intrare/ieşire:kangaroo.in, kangaroo.outSursăCEOI 2016, Ziua 1
AutorAdrian Panaete, Pit-Rada VasileAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inkangaroo.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?