El Psy Kongroo.
Омкар смотрит Steins;Gate.
В Steins;Gate, Окабэ Ринтару нужно выполнить \(n\) заданий (\(1 \leq n \leq 2 \cdot 10^5\)). К сожалению, он не знает, когда ему нужно выполнить задания.
Изначально время равно \(0\). Путешествие во времени происходит по следующим правилам:
Для каждого \(k = 1, 2, \ldots, n\), Окабэ поймет в момент времени \(b_k\), что он должен был выполнить \(k\)-е задание в момент времени \(a_k\) (\(a_k < b_k\)).
Когда он осознает это, если \(k\)-е задание уже было выполнено в момент времени \(a_k\), Окабэ сохраняет обычный ход времени. В противном случае, он перемещается во времени к моменту \(a_k\).
Если Окабэ переместится во времени к моменту \(a_k\), то все задания после этого времени снова станут невыполненными. То есть, для каждого \(i\), если \(a_i>a_k\), \(a_i\) станет невыполненным, если оно было выполненным (если оно было невыполненным, ничего не изменится).
У Окабэ плохая память, поэтому он может путешествовать во времени во время \(a_k\) только сразу после того, как попадет во время \(b_k\) и узнает, что он должен был выполнить \(k\)-е задание во время \(a_k\). То есть, даже если Окабэ уже выполнял \(k\)-е задание ранее, он не вспомнит об этом до того, как опять наткнется на информацию об этом задании в момент времени \(b_k\).
Пожалуйста, ознакомьтесь с примером путешествия во времени, который приведен в примечаниях.
Существует определенный набор \(s\) заданий, такой, что в первый момент, когда все задания из \(s\) будут одновременно выполнены (независимо от того, выполнены ли в данный момент какие-либо другие задания), произойдет забавная сцена. Окабэ нравится эта сцена, и он хочет знать, сколько раз Окабэ будет перемещаться во времени, прежде чем эта сцена произойдет. Найдите это число по модулю \(10^9 + 7\). Можно доказать, что в конце концов все \(n\) заданий будут выполнены, поэтому ответ всегда существует.
Выходные данные
Выведите одно целое число — количество раз, которое время Окабэ будет путешествовать во времени, пока все задачи в наборе \(s\) не будут одновременно завершены, по модулю \(10^9 + 7\),
Примечание
Для первого примера все задания должны быть выполнены, чтобы произошла забавная сценка.
Первоначально время равно \(0\). Ничего не происходит до момента времени \(3\), когда Окабэ понимает, что он должен был выполнить \(2\)-ю задачу в момент времени \(2\). Затем он перемещается во времени в момент времени \(2\) и выполняет задание.
Поскольку задание уже выполнено, он не перемещается во времени снова, когда время снова становится \(3\). Однако в момент времени \(4\) он перемещается в момент времени \(1\), чтобы выполнить \(1\)-е задание.
Это отменяет \(2\)-е задание. Это означает, что задание \(2\) на данный момент не выполнено, а значит, смешная сцена не произойдет в этот момент, несмотря на то что задание \(1\) на данный момент выполнено, и Окабэ ранее выполнял задачу \(2\).
Когда снова наступит время \(3\), он снова вернется во время \(2\) и снова выполнит \(2\)-е задание.
Теперь все задания выполнены, а Окабэ успел переместиться во времени \(3\) раза.
Во втором примере Окабэ предстоит выполнить те же задания. Однако на этот раз для того, чтобы произошла забавная сцена, необходимо выполнить только первое задание. Прочитав приведенный выше пример, вы можете увидеть, что это произойдет, как только Окабэ переместится во времени в момент \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 4
2 3
2
1 2
|
3
|
|
2
|
2
1 4
2 3
1
1
|
2
|
|
3
|
1
1 2
1
1
|
1
|
|
4
|
6
10 12
3 7
4 6
2 9
5 8
1 11
3
2 4 6
|
17
|
|
5
|
16
31 32
3 26
17 19
4 24
1 28
15 21
12 16
18 29
20 23
7 8
11 14
9 22
6 30
5 10
25 27
2 13
6
3 8 2 5 12 11
|
138
|