Laiko ribojimas: 6s

Atminties ribojimas: 256MB

Duomenų failas: cempionatas.in

Rezultatų failas: cempionatas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Šachmatų čempionatas

Bitijoje vyksta šachmatų čempionatas, kuriame varžysis Nuliškių ir Vienetiškių rinktinės. Kiekvieną komandą sudaro po N žaidėjų. Čempionato metu bus sužaista N partijų – kiekvienoje iš jų susigrums žaidėjų pora, kurios vienas narys iš Nuliškių, kitas – iš Vienetiškių rinktinės. Laimėta partija komandai duoda vieną tašką, o pralaimėjimas taškų nei duoda, nei atima.

Čempionatas prasideda burtų traukimu, kurio metu išsiaiškinamos visų žaidimų poros. Kiekvienas žaidėjas iš pirmos komandos žaidžia su vienu žaidėju iš antros komandos (ir atvirkščiai).

Nuliškių mokslininkai neseniai atliko tyrimą, kurio metu nustatė abiejų komandų žaidėjų meistriškumo lygį, išreiškiamą sveikuoju skaičiumi. Jokie du iš visų 2N žaidėjų nėra vienodo lygio. Kad ir kaip bebūtų keista, žaidime visada laimi žaidėjas, kurio lygis aukštesnis.

Čempionato organizatorius pasiekė informacija, jog aukšto rango Nuliškių pareigūnas ponas N. iš didelės sumos susilažino, jog jo komanda laimės S taškų skirtumu. Kaipmat iš labai svarbių asmenų atėjo „rekomendacija“ burtų traukimą „suorganizuoti“ taip, kad Nuliškių rinktinė čempionate surinktų lygiai S taškų daugiau, negu Vienetiškių rinktinė.

Parašykite programą, kuri rastų skirtingų burtų traukimo rezultatų kiekį, po kurių Nuliškių rinktinė turėtų lygiai S pergalių daugiau, negu Vienetiškių rinktinė. Du burtų traukimo rezultatai laikomi skirtingais, jei yra bent vienas žaidėjas, kuris juose turi skirtingus varžovus.

Pradiniai duomenys

Pirmoje eilutėje yra du sveikieji skaičiai N ir S (1\\leqN\\leq500, 1\\leqS\\leqN). Antroje ir trečioje eilutėse yra po N sveikųjų skaičių – i-asis antros eilutės skaičius reiškia i-ojo Nuliškių rinktinės žaidėjo mestriškumo lygį, o j-asis trečios eilutės – j-ojo Vienetiškių rinktinės žaidėjo meistriškumo lygį. Visi meistriškumo lygį žymintys skaičiai yra skirtingi bei priklauso intervalui [0;10^9].

Rezultatai

Išspausdinkite vieną sveikąjį skaičių – kiek gali būti skirtingų burtų traukimo rezultatų, po kurių Nuliškių komanda čempionate surinktų lygiai S taškų daugiau už Vienetiškių komandą. Skaičius gali būti pakankamai didelis, todėl jį išspausdinkite moduliu 1000000009.

Pavyzdys

Duomenys Rezultatai 
4 2
5 35 15 45
40 20 10 30
 
4
 
2 2
3 4
1 2
 
2

Paaiškinimas

Pirmame pavyzdyje priimtini šie burtų traukimo rezultatai: (5-40, 35-20, 15-10, 45-30), (5-40, 45-20, 15-10, 35-30), (45-40, 5-20, 15-10, 35-30) ir (45-40, 35-20, 15-10, 5-30).