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

Poveste şi cerinţă...

Se da un numar natural $VAL$, si un sir $A$, format din $N$ numere naturale, din intervalul $[0, VAL - 1]$. Asupra sirului $A$ se impun o serie de $M$ restrictii de forma: suma elementelor intre $X$ si $Y$ trebuie sa fie egala cu $Z$, $modulo VAL$. Dandu-se $VAL$, $N$ si cele $M$ restrictii, sa se calculeze numarul de siruri $A$ care respecta toate cele $M$ restrictii, si sa se afiseze $modulo 666013$.

h2. Date de intrare

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

Fişierul de intrare $restrictii.in$ va contine pe prima linie numerele $N$, $M$ si $VAL$. Urmatoarele $M$ linii vor avea formatul $X Y Z$, cu semnificatia din enunt.

h2. Date de ieşire

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

În fişierul de ieşire $restrictii.out$ se va afla pe prima linie raspunsul cautat, **$modulo 666013$**.

h2. Restricţii

* $1 ≤ N ≤ 50.000$          (lungimea sirului)
* $1 ≤ M ≤ 100.000$         (numarul de restrictii)
* $1 ≤ VAL ≤ 1.000.000.000$ (atat numerele din sir, cat si sumele din restrictii sunt modulo VAL)
* Rezultatul se afiseaza modulo $666013$.

* $1 ≤ N ≤ 50.000$
* $1 ≤ M ≤ 100.000$
* $1 ≤ VAL ≤ 1.000.000.000$

h2. Exemplu