transport

Anul 1905

Un stat din America de Sud și-a propus investiții majore în infrastructura feroviară. Brazilianul Badinho este managerul unei companii de transport feroviar pe o magistrală importantă. De-a lungul magistralei se află $N$ stații, numerotate de la $1$ la $N$. Fiecărei stații îi corespunde un număr $X_i$ care reprezintă numărul de kilometri de la începutul magistralei până la stația $i$ ($X_1 = 0$). Pentru simplitate Badinho reprezintă magistrala ca o dreaptă, iar stațiile ca puncte pe dreapta respectivă, stația $i$ aflându-se la coordonata $X_i$.

O rută reprezintă o submulțime de cel puțin 2 stații dintre cele $N$, cu semnificația că în aceste stații se vor face opriri. Orice rută operată de Badinho are 2 stații numite capete, definite ca fiind cea mai apropiată stație, inclusă în rută, de începutul magistralei respectiv cea mai îndepărtată stație, inclusă în rută, de începutul magistralei.

Compania lui Badinho va primi o subvenție pentru deschiderea unei noi rute, care va fi proporțională cu lungimea rutei deschise. Mai exact, Badinho va primi $C$ reali (realul este moneda națională a Braziliei) pentru fiecare kilometru din noua rută. Lungimea rutei se definește ca fiind distanța dintre capete.

Badinho poate deschide două tipuri de rute:

• Regio — se fac opriri în toate stațiile dintre cele două capete
• Expres — unele stații dintre cele două capete pot fi traversate fără a opri în ele

Pentru a deschide o rută Badinho trebuie să construiască câte un depou în capetele rutei respective. Costul pentru a construi un depou în stația $i$ este $D_i$ reali.

Știind că Badinho trebuie să cheltuiască întreaga sumă pe care ar primi-o dintr-o subvenție, să se determine:

1. Numărul de moduri de a deschide o rută de tip Regio, $\text{modulo }10^9 + 7$
2. Numărul de moduri de a deschide o rută de tip Expres, $\text{modulo }10^9 + 7$

Date de intrare

În fișierul transport.in se află:

• Pe prima linie tipul cerinței $T$, care poate avea valoarea $1$ sau $2$.
• Pe a doua linie $N$ și $C$, separate printr-un spațiu, reprezentând numărul de stații, respectiv suma primită per kilometru ca subvenție.
• Pe următoarele $N$ linii, pe linia $i + 2$ se află câte o pereche $X_i$ și $D_i$, separate printr-un spațiu, reprezentând distanța la care se află stația $i$ față de începutul magistralei, respectiv costul de a contrui un depou în stația $i$.

Date de ieșire

În fișierul transport.out se va afișa:

• Dacă $T = 1$, numărul de moduri de a deschide o rută de tip Regio, $\text{modulo }10^9 + 7$
• Dacă $T = 2$, numărul de moduri de a deschide o rută de tip Expres, $\text{modulo }10^9 + 7$

Restricții

• Două rute se consideră distincte dacă diferă prin cel puțin o stație.
• $2 \leq N \leq 200\ 000$, $1 \leq C \leq 10^9$
• $0 \leq X_i, D_i \leq 10^9\ \forall \ 1 \leq i \leq N$
• $X_1 = 0$
• Șirul $X$ este sortat strict crescător: $X_i \lt X_j \ \forall \ 1 \leq i \lt j \leq N$.
• Toate liniile de cale ferată ale magistralei sunt deja construite, singurele costuri pe care le va suporta Badinho sunt cele de construire a depourilor.

Subtask 1 (12 puncte)

• $T = 1$, $N \leq 1\ 000$

Subtask 2 (26 puncte)

• $T = 1$, $N \leq 200\ 000$

Subtask 3 (6 puncte)

• $T = 2$, $N \leq 15$

Subtask 4 (15 puncte)

• $T = 2$, $N \leq 1\ 000$

Subtask 5 (41 puncte)

• $T = 2$, $N \leq 200\ 000$

Exemplul 1

transport.in

1
5 1
0 2
1 1
3 10
4 15
6 4

transport.out

2

Explicație

Rutele posibile în condițiile cerinței 1 sunt: $\{1,2,3,4,5\}$, $\{2,3,4,5\}$.
Ruta $\{1,2,3,4,5\}$ conține opriri în stațiile $1$, $2$, $3$, $4$, $5$. Stațiile $1$ și $5$ sunt cele $2$ capete. Suma primită din subvenție este: $1 \cdot (6-0) = 6$ reali ($6-0$ reprezintă distanța dintre stația $1$ și $5$), iar costul de construire a celor $2$ depouri e: $2+4 = 6$ reali.

Exemplul 2

transport.in

2
5 1
0 2
1 1
3 10
4 15
6 4

transport.out

12

Explicație

Rutele posibile în condițiile cerinței 2 sunt: $\{1,5\}$, $\{1,2,5\}$, $\{1,3,5\}$, $\{1,4,5\}$, $\{1,2,3,5\}$, $\{1,2,4,5\}$, $\{1,3,4,5\}$, $\{1,2,3,4,5\}$, $\{2,5\}$, $\{2,3,5\}$, $\{2,4,5\}$, $\{2,3,4,5\}$.
Ruta $\{1,2,5\}$ conține opriri în stațiile $1$, $2$, $5$. Stațiile $1$ și $5$ sunt cele $2$ extreme. Suma primită din subvenție e: $1 \cdot (6-0) = 6$ reali, iar costul de construire a celor $2$ depouri e: $2+4 = 6$ reali.