- Time limit: 1.00 s
- Memory limit: 512 MB
Annettuna on lista, jossa on n eri kokonaislukua. Tehtäväsi on laskea, monellako tavalla listan voi järjestää niin, että aina kun jokin luku on pienempi kuin edellinen luku, lukujen ero on enintään x.
Esimerkiksi kun lista on [1,2,3] ja x=1, mahdolliset järjestykset ovat [1,2,3], [1,3,2], [2,1,3] ja [3,2,1].
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku t: testien määrä.
Tämän jälkeen jokainen testi kuvataan kahdella rivillä. Ensimmäisellä rivillä on luvut n ja x, ja toisella rivillä on listan sisältö a_1,a_2,\dots,a_n.
Tuloste
Tulosta jokaisen testin vastaus. Koska vastaus voi olla suuri luku, tulosta se modulo 10^9+7.
Esimerkki
Syöte:
3 1 5 1 3 1 1 2 3 8 42 8 2 100 95 999 1 77 6
Tuloste:
1 4 144
Osatehtävä 1 (26 pistettä)
- 1 \le t \le 100
- 1 \le n \le 8
- 1 \le a_i, x \le 100
Osatehtävä 2 (74 pistettä)
- 1 \le t \le 100
- 1 \le n \le 100
- 1 \le a_i, x \le 1000