Фермер Джон нанимает нового вожака стада для своих коров.
Для этого он проинтервьюировал \(N\) (\(2 \leq N \leq 10^9\)) коров.
Каждому он назначил "уровень компетенции" - число не более \(C\)
(\(1 \leq C \leq 10^4\)).
Потому что он провёл много интервью, ФД забыл все эти уровни компетенции.
Однако он запомнил \(Q\) (\(1 \leq Q \leq \min(N - 1, 100)\)) пар чисел
\((a_i, h_i)\) где \(h_i\) - номер первой коровы, с уровнем компетенции
строго большим чем у коров от \(1\) до \(a_i\)
(\(1 \leq a_i < h_i \leq N\)).
ФД сказал Вам \(Q\) пар \((a_i, h_i)\). Помогите ему посчитать
сколько последовательностей уровней компетенции соответствуют этой
информации. Поскольку число очень большое, выводите его по модулю \(10^9 + 7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\),
\(Q\),
\(C\).
Каждая из следующих \(Q\) строк содержит пару \((a_i, h_i)\).
Гарантируется, что все \(a_j\) различны.
ФОРМАТВЫВОДА (на экран / stdout):
Количество по модулю \(10^9+7\) последовательностей компетенций,
соответствующих информации ФД.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2 3
2 3
4 5
|
6
|