Problem description

Januszex S.A. otwiera nowy sklep. Tak się akurat złożyło, że budynek, który wybrał Pan Janusz jako halę sprzedaży jest bardzo długi i wąski, dlatego udało się w nim postawić jedynie jeden bardzo długi regał, na którym położono po kolei N typów przedmiotów ponumerowanych kolejnymi liczbami naturalnymi od 1 do N zgodnie z kolejnością ich występowania na półkach sklepowych od wejścia do linii kas. Sklep jest oczywiście dobrze wyposażony, więc każdego typu przedmiotu jest dostatecznie dużo by zadowolić nawet najtwardszych hurtowników kupujących po parę miliardów sztuk.

Pan Janusz doskonale zna swoich klientów. To zakupoholicy – wchodzą z ustalonym budżetem do sklepu (tylu bajtalarów ile mają na koncie, w portfelu i dostępnej linii kredytowej), idą obok kolejnych produktów aż im się któryś spodoba – wówczas uruchamia się tak zwany ,,szał zakupowy’’ – tzn. od tego momentu biorą z półek wszystko jak leci póki mają pieniądze. Innymi słowy, każdy klient wybiera w sklepie produkt o typie P_i i brnąc do przodu do linii kas kupuje każdego napotkanego towaru tyle ile może (koszyki w sklepie są bardzo pojemne, więc klientów ogranicza jedynie ich budżet i linia kas). Pan Janusz zastanawia się teraz ile towarów sprzeda. Pomóż mu!

Napisz program, który: wczyta opis towarów w sklepie oraz opis nadchodzących do sklepu klientów, wyznaczy łączną liczbę sprzedanych towarów i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz Q oddzielone pojedynczym odstępem – są to kolejno: liczba typów przedmiotów w sklepie oraz liczba klientów. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych A_i pooddzielanych pojedynczymi odstępami – ceny pojedynczych sztuk kolejnych typów produktów sprzedawanych w sklepie. W kolejnych Q wierszach znajduje się opis kolejnych klientów. Opis każdego klienta składa się z dwóch liczb naturalnych B_i oraz P_i, oddzielonych pojedynczym odstępem – są to kolejno budżet i-tego klienta oraz typ produktu, od którego rozpoczyna się szał zakupowy.

Wyjście

W pierwszym (jedynym) wierszu wyjścia należy wypisać jedną liczbę naturalną – resztę z dzielenia przez 10⁹ + 7 łącznej liczby sprzedanych produktów.

Ograniczenia

1 ≤ N ≤ 200 000, 1 ≤ Q ≤ 200 000, 1 ≤ A_i ≤ 10¹⁸, 1 ≤ B_i ≤ 10¹⁸, 1 ≤ P_i ≤ N.

Przykład

6 3
7 4 9 2 1 13
30 3
7 5
13 1

15