Laiko ribojimas: 2s

Atminties ribojimas: 256MB

Duomenų failas: grupes.in

Rezultatų failas: grupes.out

Jei norite pateikti savo sprendimą - prisijunkite.

Grupės

Klasėje yra n mokinių dirbančių grupėmis prie projektų. Mokiniai pasidalina į grupes (kai kurie mokiniai gali būti grupėmis po vieną) ir dirba prie atskirų uždavinių. Kai visi toje pačioje grupėje esantys mokiniai baigia uždavinį, jie tarpusavyje aptaria rezultatus. i-tajam mokiniui prireikia a_i minučių padaryti uždavinį.

Kadangi mokiniai dirba skirtingu greičiu, greičiau dirbantiems mokiniams gali būti nuobodu laukti lėčiau dirbančių savo grupės narių. Tarkime, jog grupės disbalansas, tai didžiausio grupėje esančio a_i bei mažiausio grupėje esančio a_i skirtumas. (Jei grupę sudaro vienas asmuo, disbalansas bus lygus 0). Jūsų užduotis - rasti, kiek yra skirtingų atvejų padalinti mokinius į grupes taip, kad visų grupių disbalansų suma būtų ne didesnė nei k.

Du padalinimo atvejai laikomi skirtingais, jeigu egzistuoja tokia mokinių pora, kurie vienu atveju yra toje pačioje grupėje, o kitu atveju yra skirtingose grupėse.

Pradiniai duomenys

Pirmoje eilutėje yra du skaičiai n ir k (1\\leqn\\leq200,0\\leqk\\leq1000).

Antroje eilutėje yra n skaičių a_i (1\\leqa_i\\leq500) - kiek minučių užtrunka i-tajam mokiniui padaryti uždavinį.

Rezultatai

Išveskite vieną skaičių - keliais skirtingais būdais galima padalinti mokinius į grupes moduliu 10^9+7.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3 2
2 4 5
 
3