Sirdacic

Eu nu mai am nimic de spus!
Voi brațele jurând le-ați pus
Pe scut! Puterea este-n voi
Și-n zei! Dar vă gândiți, eroi,
Că zeii sunt departe, sus,
Dușmanii lângă noi!

Pe vremea Dacilor Liberi se spunea că un șir $A$ este $K$-liber dacă diferența absolută a oricare două elemente consecutive din șir nu este divizibilă cu $K$.

Cerință

Conducătorul Dacilor Liberi, Decebal, vă dă un șir $A$ de $N$ numere întregi și un număr natural $K$. Pentru ca Dacii Liberi să câștige lupta împotriva armatei conduse de Traian, tu trebuie să calculezi numărul de moduri în care putem rearanja elementele șirului $A$ astfel încât șirul rezultat să fie $K$-liber. Dacă veți reuși să găsiți răspunsul corect, lupta va fi ca și câștigată. Cum acest număr poate să fie foarte mare, se cere restul său la impărțirea cu $10^9 + 7$.

Date de intrare

Pe prima linie se află numerele $N$ și $K$ cu semnificația din cerință. A doua linie conține $N$ numere, reprezentând elementele șirului $A$.

Date de ieșire

Pe prima linie din fișierul de ieșire se va afișa restul la $10^9 + 7$ al numărului pe care Decebal vă roagă să îl calculați.

Restricții și precizări

• $1 \leq N \leq 2 \ 500$
• $2 \leq K \leq 1 \ 000 \ 000$
• $0 \leq A_{i} \leq 10^9$.

Subtask 1 (6 puncte)

• $1 \leq N \leq 10$

Subtask 2 (20 puncte)

• $1 \leq N \leq 50$

Subtask 3 (25 puncte)

• $1 \leq N \leq 200$

Subtask 4 (49 puncte)

• Fără alte restricții

Exemplul 1

stdin

5 5
1 1 6 2 3

stdout

6

Explicație

Șirurile $K$-libere sunt:
1 2 1 3 6
1 2 6 3 1
1 3 1 2 6
1 3 6 2 1
6 2 1 3 1
6 3 1 2 1

Exemplul 2

stdin

5 6
1 2 3 4 5

stdout

120

Explicație

Trăiască Dacia Liberă!!!