Šeštadieninė informatikos olimpiadininkų mokykla

Jonas labai mėgsta saldainius. Ypač stebuklingus. Pasirodo, jie leidžia Jonui labai lengvai keliauti iš vienos vietos į kitą kaip koordinačių sistemoje. Norėdamas kažkur nukeliauti, Jonas paprasčiausiai turi suvalgyti saldainį ir jis jau kitoje vietoje!

Kiekvienas saldainis nukelia Joną nuspėjamu keliu. Sakykime Jonas yra pozicijoje . Jeigu jis suvalgo saldainį ant kurio parašyti skaičiai ir , tai Jonas atsidurs vietoje . Užduotis – surasti skaičių būdų, kuriais Jonas gali valgyti saldainius, kad atsidurtų reikiamoje vietoje. Jono pradinė vieta . Būdai laikomi skirtingais, jeigu Jonas suvalgo skirtingą kiekį saldainių arba jų valgymo tvarka skiriasi. (Turėkite omenyje, Jonas gali atvykti į reikiamą vietą ir anksčiau. Taip pat, jeigu ant dviejų saldainių užrašyti vienodi skaičiai ir , tie saldainiai vis tiek laikomi skirtingais.)

Pradiniai duomenys

Pirmoje eilutėje duotas teigiamas sveikasis skaičius , nurodantis kelionių kiekį. Kiekvienos kelionės pirmoje eilutėje duoti trys sveikieji skaičiai , atitinkamai reiškiantys saldainių skaičių ir jo tikslo vietos ir koordinatės. Jono tikslas niekada nebus jo pradinė vieta. Sekančiose n eilučių duoti du skaičiai ir , reiškiantys numerius užrašytus ant kiekvieno saldainio.

Rezultatai

Kiekvienai kelionei išveskite vieną sveikąjį skaičių, reiškiantį kiek būdų Jonas gali suvalgyti saldainius, kad atsidurtų reikiamoje vietoje. Kadangi skaičiai gali būti labai dideli, rezultatus rašykite moduliu .

Pavyzdys

1
3 2 2
3 3
-1 -1
2 2

3