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 Xi care reprezintă numărul de kilometri de la începutul magistralei până la stația i (X1 = 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 Xi.

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

Cerința

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

• Numărul de moduri de a deschide o rută de tip Regio, modulo 1.000.000.007
• Numărul de moduri de a deschide o rută de tip Expres, modulo 1.000.000.007

Date de intrare

În fișierul de intrare 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 Xi și Di, separate printr-un spațiu, reprezentând distanța la care se află stația i față de începutul magistralei, respectiv costul de a construi un depou în stația i.

Date de ieșire

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

• Dacă T = 1, numărul de moduri de a deschide o rută de tip Regio, modulo 1.000.000.007
• Dacă T = 2, numărul de moduri de a deschide o rută de tip Expres, modulo 1.000.000.007

Restricții și precizări

• Două rute se consideră distincte dacă diferă prin cel puțin o stație.
• 2 ≤ N ≤ 200.000, 1 ≤ C ≤ 1.000.000.000
• 0 ≤ Xi, Di ≤ 1.000.000.000 pentru orice 1 ≤ i ≤ N
• X1 = 0
• sirul X este sortat strict crescător: Xi < Xj pentru orice 1 ≤ i < j ≤ 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
• Din cauza dimensiunilor mari, unele teste nu au fost adăugate

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 * (6 - 0) = 6 reali (6 - 0 reprezintă distanța dintre stația 1 și 5), iar costul de construire a celor 2 depouri este: 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 este: 1 * (6 - 0) = 6 reali, iar costul de construire a celor 2 depouri este: 2 + 4 = 6 reali.