Vagoane

vagoane

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

bq. Noi urmărim ... să nu fim urmăriţi!

Poveste şi cerinţă...

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 intrare

h2. Date de intrare

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

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ă.

h2. Date de ieşire

h2. Date de ieşire

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

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$**.

h2. Restricţii

h2. Restricţii

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

* $1 ≤ N ≤ 10^9^$
* $0 ≤ M ≤ 2 * 10^5^$
* $1 ≤ C ≤ 5 * 10^5^$

h2. Exemplu

* **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

table(example). |_. vagoane.in |_. vagoane.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

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") ==