CSES - Koodarit
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Yrityksessä on töissä nn koodaria, joista jokaisen koodaustaito on kokonaisluku välillä 01000 \ldots 100. Tehtäväsi on jakaa koodarit ryhmiin, jotka työskentelevät yhdessä.

Kokemuksen perusteella tiedetään, että ryhmät toimivat hyvin, kun niissä on suunnilleen samantasoisia koodareita. Ryhmän riitaisuus on parhaimman ja huonoimman koodarin taitojen ero.

Monellako tavalla voit jakaa koodarit ryhmiin niin, että ryhmien riitaisuuksien summa on enintään xx?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja xx: koodarien määrä ja suurin sallittu riitaisuuksien summa.

Toisella rivillä on nn kokonaislukua t1,t2,,tnt_1,t_2,\ldots,t_n: kunkin koodarin taitotaso.

Tuloste

Tulosta yksi kokonaisluku: mahdollisten jakojen määrä modulo 109+710^9+7.

Rajat

  • 1n1001 \le n \le 100
  • 0x50000 \le x \le 5000
  • 0ti1000 \le t_i \le 100

Esimerkki

Syöte:

3 2
2 5 3

Tuloste:

3