Školica je dečija igra naročito popularna kod učenica i učenika u osnovnoškolskom uzrastu. Igra se odvija skakutanjem na jednoj ili obe noge kroz šemu iscrtanu na tlu. Praktična je za igranje u školskom dvorištu ili na igralištu.

Šema za igru

Školica je popularna širom sveta, pa se šema kroz koju igrač skakuće razlikuje od zemlje do zemlje. Za potrebe ovog zadatka će se koristiti takozvana niz-šema. Možete je zamisliti kao niz uzastopnih kredom nacrtanih polja numerisanih od ~1~ do ~N~ ili jednostavno pogledati sliku.

Slika školice sa N=8 polja:

Pravila igre

Anja i Ema igraju najnoviju verziju školice izmišljene samo za potrebe finala Algoge Kupa. U "levo-desno" školici svaki skok mora biti u suprotnu stranu od prethodnog skoka - tj. ukoliko je prethodni skok bio na levo, sledeći mora biti na desno, i tako naizmenično. Da bi se školica uspešno prešla, potrebno je stati na svako polje tačno jednom. Njih dve se sada pitaju - koliko li načina postoji da pređu igru, ako kreću sa polja P a žele da završe na polju K (gde jedan način predstavlja redosled obilaženja polja).

Pošto broj načina može biti preveliki, ispisati rešenje po modulu ~1000000007 = (10^9 + 7)~.

Opis ulaza

U prvoj i jednoj liniji standardnog ulaza nalaze se tri broja ~N, P, K~, koji redom označavaju broj polja šeme školice, početno i krajnje polje.

Opis izlaza

U prvoj liniji standardnog izlaza ispisati broj načina na koji je moguće preći igru, po modulu 1000000007.

Primer

4 2 3

2

Objašnjenje test primera:

Postoje samo 2 načina da uspešno pređemo školicu: 2 -> 1 -> 4 -> 3 2 -> 4 -> 1 -> 3

Ograničenja i podzadaci

~2 \le N \le 2000~
~1 \le P,K \le N~

Test primeri su podeljeni u 4 disjunktne grupe:

• U test primerima vrednim 5 poena: ~2 \le N \le 8~
  
• U test primerima vrednim 25 poena: ~2 \le N \le 40~
  
• U test primerima vrednim 30 poena: ~2 \le N \le 200~
  
• U test primerima vrednim 40 poena: Nema dodatnih ograničenja.