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

In timpul confruntarii finale dintre Comisarul Miclovan si pistolarii lui Semaca de la depozitul de cherestea, la Gara de Nord are loc o inspectie - se zvoneste ca in trenul de 10 se gasesc ilegal peste 7 vagoane (mai exact **N**) pline cu... mazare, rosii si fasole. Cum intunericul este gros, distingerea unui material de altul nu este treaba usoara, **M** caini special dresati au fost adusi spre a grabi si eficientiza inspectia. Cele N vagoane ale trenului sunt dispuse secvential, unul dupa unul dupa locomotiva, numerotate cu intregi consecutivi de la 1 la N. Fiecare caine poate fi folosit o singura data de-a lungul verificarii, in vederea testarii unui singur interval

In timpul confruntarii finale dintre Comisarul Miclovan si pistolarii lui Semaca de la depozitul de cherestea, la Gara de Nord are loc o inspectie - se zvoneste ca in trenul de 10 se gasesc ilegal peste 7 vagoane pline cu... graunte si cartofi. Cum intunericul este gros, distingerea unui material de altul nu este o treaba usoara, asa ca **M** caini special dresati au fost adusi spre a grabi si eficientiza inspectia. Cele **N** vagoane ale trenului sunt dispuse secvential, unul dupa altul in spatele locomotivei, numerotate cu numere intregi consecutive de la 1 la N. Fiecare caine poate fi folosit o singura data de-a lungul verificarii, in vederea testarii unui singur interval compact de vagoane. Un caine va latra imediat daca intalneste 2 vagoane cu acelasi continut in intervalul pe care acesta il verifica (altfel acesta nu va mai latra deloc). Daca un singur caine latra, toata actiunea este compromisa, asa ca tu va trebui sa calculezi (stiind ca exista **C** tipuri diferite de continuturi pentru un vagon si intervalele de patrula pentru fiecare caine) numarul de moduri de a incarca fiecare vagon cu cate unul din cele C continuturi astfel incat actiunea sa nu fie compromisa.

h2. Date de intrare

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

Fişierul de intrare $vagoane.in$ contine pe prima linie numerele **N**, **M** si **C**, in ordine si separate prin cate un spatiu.
Pe fiecare din urmatoarele M linii se afla cate doua numere intregi pozitive **L** si **R**, astfel incat $1 ≤ L ≤ R ≤ N$, reprezentand capetele intervalului de vagoane pe care cainele respectiv patruleaza.

h2. Date de ieşire

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

Fişierul de ieşire $vagoane.out$ trebuie sa contina un singur numar intreg nenegativ **ANS**, reprezentand numarul de moduri de a umple vagoanele trenului.

h2. Restricţii

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

* $1 ≤ N ≤ 1000000000$
* $1 ≤ M ≤ 200000$
* $1 ≤ C ≤ 500000$

h2. Exemplu
table(example). |_. vagoane.in |_. vagoane.out |

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

| 3 2 3
  1 2
  2 3
| 12

|
h3. Explicaţie