Sirdacic

Time limit: 0.1s Memory limit: 512MB Input: Output:

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 AA este KK-liber dacă diferența absolută a oricare două elemente consecutive din șir nu este divizibilă cu KK.

Cerință

Conducătorul Dacilor Liberi, Decebal, vă dă un șir AA de NN numere întregi și un număr natural KK. 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 AA astfel încât șirul rezultat să fie KK-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 109+710^9 + 7.

Date de intrare

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

Date de ieșire

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

Restricții și precizări

  • 1N2 5001 \leq N \leq 2 \ 500
  • 2K1 000 0002 \leq K \leq 1 \ 000 \ 000
  • 0Ai1090 \leq A_{i} \leq 10^9.

Subtask 1 (6 puncte)

  • 1N101 \leq N \leq 10

Subtask 2 (20 puncte)

  • 1N501 \leq N \leq 50

Subtask 3 (25 puncte)

  • 1N2001 \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 KK-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ă!!!

Log in or sign up to be able to send submissions!