Șir dacic

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 2500$
• $2 \leq K \leq 1 000 000$
• $0 \leq A_{i} \leq 10^9$
• Pentru $6$ puncte: $1 \leq N \leq 10$
• Pentru $20$ de puncte: $1 \leq N \leq 50$
• Pentru $25$ de puncte: $1 \leq N \leq 200$
• Pentru $49$ de puncte: Fără alte restricții

Exemple

Intrare

5 5
1 1 6 2 3

Ieșire

6

Intrare

5 6
1 2 3 4 5

Ieșire

120

Explicații

Pentru primul exemplu: Ș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

Pentru al doilea exemplu: Trăiască Dacia Liberă!!!