У Фермера Джона есть \(N\) коров (\(2 \leq N \leq 5\cdot 10^6\)) и пытается заставить
их отсортировать неотрицательный целочисленный массив \(A\) длины \(N\), полагаясь на их
лень. У него много тяжелых коробок, поэтому он выстраивает коров одну за другой,
где корова \(i+1\) находится за коровой \(i\), и дает \(a_i\) коробок корове \(i\)
(\(0\le a_i\)).
Коровы по своей природе ленивы, поэтому они всегда ищут способ передать свою работу
кому-то другому. От коровы \(1\) до \(N-1\) по порядку каждая корова смотрит на корову позади себя.
Если у коровы \(i\) строго больше коробок, чем у коровы \(i+1\), корова \(i\) считает, что это
«несправедливо» и отдает одну из своих коробок корове \(i+1\). Этот процесс повторяется,
пока каждая корова не будет удовлетворена.
Фермер Джон пометил количество ящиков \(b_i\), которое каждая корова \(i\)
держит и создал массив \(B\) из этих величин. Если \(B = sorted(A)\) тогда
ФД счастлив. К несчастью. ФД забыл все кроме \(Q\) величин массива \(A\).
(\(2 \leq Q \leq \min(N, 100)\)). К счастью, эти величины включают количество ящиков,
которое он собирается дать первой и последней корове. Каждое число, которое помнит ФД
задано в виде \(c_i \; v_i\), представляющее, что \(a_{c_i}=v_i\).
(\(1 \leq c_i \leq N\), \(1\le v_i\le 10^9\)). Определите количество различных способов,
которыми могут быть заполнены пропущенные величины так чтобы ФД был счастливым.
ответ выводите по модулю \(10^9+7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит два разделённых пробелом целых числа
\(N\) и
\(Q\)
представляющие количество коров и запросов соответственно.
Следующие \(Q\) строк содержат два разделённых пробелом целых числа \(c_i \; v_i\)
представляющих что корова \(c_i\) изначально держит \(v_i\) ящиков. Гарантируется, что
\(c_1 = 1\), \(c_Q = N\), и \(c_i < c_{i+1}\) (порядок коров строго возрастающий).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите количество способов по модулю \(10^9+7\), которыми могут быть назначены
значения \(a_i\), так, что ФД будет счастлив после того, как коровы выполнят
ленивую сортировку. Гарантируется существование как минимум одного такого
назначения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 3
3 2
|
2
|