== 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 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.
bq. Noi urmărim ... să nu fim urmăriţi!
h2. Date de intrare
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.
Brigada Diverse a fost informată că în trenul de ora zece sunt plasate peste $7$ vagoane pline cu ... grăunţe şi cartofi. Se ştie că pe întuneric distingerea unui material de altul nu este o treaba uşoară, aşa că se va organiza o inspecţie în depoul Gării de Nord, cu participarea a $M$ câini special dresaţi. Cele $N$ vagoane ale trenului sunt dispuse secvenţial, unul după altul în spatele locomotivei, fiind numerotate cu numere întregi consecutive de la $1$ la $N$. Fiecare câine poate fi folosit o singură dată de-a lungul verificării, în vederea testării unui singur interval compact de vagoane. Un câine va lătra imediat dacă întâlneşte $2$ vagoane cu acelaşi conţinut în intervalul pe care acesta îl verifică (altfel acesta nu va lătra deloc). Dacă un singur câine latră, întregul transport va fi periclitat, aşa că voi va trebui să calculaţi numărul de moduri de a încărca fiecare vagon cu câte unul din cele $C$ conţinuturi posibile astfel încât acţiunea să nu fie compromisă.
h2. Date de ieşire
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. Date de intrare
h2. Restricţii
Fişierul de intrare $vagoane.în$ conţine pe prima linie numerele $N$, $M$ şi $C$, în ordine şi separate prin câte un spaţiu.
Pe fiecare din următoarele M linii se află câte două numere întregi pozitive $L$ şi $R$ astfel încât $1 ≤ L ≤ R ≤ N$, reprezentând capetele intervalului de vagoane pe care câinele respectiv patrulează.
* $1 ≤ N ≤ 1000000000$
* $1 ≤ M ≤ 200000$
* $1 ≤ C ≤ 500000$
h2. Date de ieşire
h2. Exemplu
Fişierul de ieşire $vagoane.out$ trebuie să conţină un singur număr întreg nenegativ $ANS$, reprezentând numărul de moduri de a umple vagoanele trenului **modulo $1000000007$**.
table(example). |_. vagoane.in |_. vagoane.out |
| 3 2 3
1 2
2 3
| 12
h2. Restricţii
* $1 ≤ N ≤ 10^9^$
* $0 ≤ M ≤ 2 * 10^5^$
* $1 ≤ C ≤ 5 * 10^5^$
* **Atenţie!** Volum mare de date de intrare, vă recomandăm să optimizaţi citirea folosindu-va de "acest cod":http://pastebin.com/dfEATDDB.
* **Atentie!** Fiecare subtask are testele grupate!
* **Subtask 1 (10 puncte):** $M = 0$ (Feedback testul 1)
* **Subtask 2 (20 puncte):** $N ≤ 1000, M ≤ 2000$ (Feedback testul 2)
* **Subtask 3 (30 puncte):** $N ≤ 10^5^$
* **Subtask 4 (40 puncte):** Restricţii iniţiale (Feedback testele 7 si 8)
h2. Exemplu
table(example). |_. vagoane.în |_. vagoane.out |
| 3 2 3
1 2
2 3
| 12
|
h3. Explicaţie
h3. Explicaţie
...
Cele 12 metode de a încărca trenul sunt, dacă codificăm cele 3 încărcături posibile cu numerele $1$, $2$ şi $3$:
$1 2 1$
$1 2 3$
$1 3 1$
$1 3 2$
$2 1 3$
$2 1 2$
$2 3 1$
$2 3 2$
$3 1 2$
$3 1 3$
$3 2 1$
$3 2 3$
== include(page="template/taskfooter" task_id="vagoane") ==
