== 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 de pe pozitiile cuprinse intre $X$ si $Y$ (inclusiv $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
table(example). |_. restrictii.in |_. restrictii.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|5 5 6
1 5 2
3 4 5
4 5 0
4 4 4
3 5 1
| 6|
| 3 3 5
1 3 2
1 2 3
3 3 3
| 0
|

h3. Explicaţie

...

Pentru primul exemplu solutiile sunt $1 0 1 4 2$, $3 4 1 4 2$, $4 3 1 4 2$, $2 5 1 4 2$, $0 1 1 4 2$ si $5 2 1 4 2$
 
Pentru al doilea exemplu nu exista nicio solutie sa satisfaca toate cele 3 restrictii.

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

7764