== include(page="template/taskheader" task_id="elemente") ==

Poveste şi cerinţă...

SMB a descoperit o problema cu siruri de numere. Fiind dat un sir cu $N$ numere naturale, SMB trebuie sa gaseasca numarul de subsiruri distincte care respecta proprietatea ca diferenta dintre oricare doua numere ale subsirului este cel mult egala cu $K$.

h2. Date de intrare

Fişierul de intrare $elemente.in$ ...

Fişierul de intrare $elemente.in$ contine pe prima linie doua numere naturale, $N$ si $K$, separate de un singur spatiu, avand semificatia din enunt. Pe urmatoarele $N$ linii urmeaza elementele sirului initial, cate unul pe o linie.

h2. Date de ieşire

În fişierul de ieşire $elemente.out$ ...

În fişierul de ieşire $elemente.out$ se va afla un singur numar natural $Res$, care reprezinta restul impartirii numarului de subsiruri distincte cu proprietatea ceruta la $1 000 003$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ 1 000 000 000$
* Numerele sirului sunt numere naturale mai mici sau egale cu $1 000 000 000$

h2. Exemplu