bq. Noi urmarim ... sa nu fim urmariti!
Brigada Diverse a fost informata ca in trenul de ora zece sunt plasate peste 7 vagoane pline cu ... graunte si cartofi. Se stie ca pe intuneric distingerea unui material de altul nu este o treaba usoara, asa ca se va organiza o inspectie in depoul Garii de Nord, cu participarea a **M** caini special dresati. Cele **N** vagoane ale trenului sunt dispuse secvential, unul dupa altul in spatele locomotivei, fiind 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 latra deloc). Daca un singur caine latra, intregul transport va fi periclitat, asa ca voi va trebui sa calculati numarul de moduri de a incarca fiecare vagon cu cate unul din cele **C** continuturi posibile astfel incat actiunea sa nu fie compromisa.
Brigada Diverse a fost informata ca in trenul de ora zece sunt plasate peste $7$ vagoane pline cu ... graunte si cartofi. Se stie ca pe intuneric distingerea unui material de altul nu este o treaba usoara, asa ca se va organiza o inspectie in depoul Garii de Nord, cu participarea a $M$ caini special dresati. Cele $N$ vagoane ale trenului sunt dispuse secvential, unul dupa altul in spatele locomotivei, fiind 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 latra deloc). Daca un singur caine latra, intregul transport va fi periclitat, asa ca voi va trebui sa calculati numarul de moduri de a incarca fiecare vagon cu cate unul din cele $C$ continuturi posibile astfel incat actiunea sa nu fie compromisa.
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.
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
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 **modulo 1000000007**.
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 **modulo $1000000007$**.
h2. Restricţii
* 1 ≤ **N** ≤ 1000000000
* 0 ≤ **M** ≤ 200000
* 1 ≤ **C** ≤ 500000
* **Subtask 1 (10 puncte):** **M** = 0
* **Subtask 2 (20 puncte):** **N** ≤ 1000, **M** ≤ 2000
* **Subtask 3 (30 puncte):** **N** ≤ 100000
* $1 ≤ N ≤ 1000000000$
* $0 ≤ M ≤ 200000$
* $1 ≤ C ≤ 500000$
* **Subtask 1 (10 puncte):** $M$ = 0
* **Subtask 2 (20 puncte):** $N$ ≤ 1000, $M$ ≤ 2000
* **Subtask 3 (30 puncte):** $N$ ≤ 100000
* **Subtask 4 (40 punctE):** Restrictii initiale
h2. Exemplu
