CSES - Putka Open 2020 – 5/5 - Järjestys
  • 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