G. Омкар и путешествия во времени
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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$$$ заданий будут выполнены, поэтому ответ всегда существует.

Входные данные

Первая строка содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — количество заданий, которые должен выполнить Окабэ.

Далее следует $$$n$$$ строк. В $$$k$$$-й из этих строк содержатся два целых числа $$$a_k$$$ и $$$b_k$$$ ($$$1 \leq a_k < b_k \leq 2n$$$)  — время, в которое Окабэ должен выполнить $$$k$$$-ю задачу и время, когда он узнает об этом соответственно. Все $$$2n$$$ этих времен попарно различны (поэтому каждое время от $$$1$$$ до $$$2n$$$ включительно встречается во входных данных ровно один раз).

Следующая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq n$$$)  — размер набора $$$s$$$ задач, которые приводят к смешной сцене.

Последняя строка содержит $$$t$$$ целых чисел $$$s_1, s_2, \ldots, s_t$$$  — ($$$1 \leq s_k \leq n$$$, числа $$$s_1, s_2, \ldots, s_t$$$ различны)  — множество $$$s$$$ задач.

Выходные данные

Выведите одно целое число  — количество раз, которое время Окабэ будет путешествовать во времени, пока все задачи в наборе $$$s$$$ не будут одновременно завершены, по модулю $$$10^9 + 7$$$,

Примеры
Входные данные
2
1 4
2 3
2
1 2
Выходные данные
3
Входные данные
2
1 4
2 3
1
1
Выходные данные
2
Входные данные
1
1 2
1
1
Выходные данные
1
Входные данные
6
10 12
3 7
4 6
2 9
5 8
1 11
3
2 4 6
Выходные данные
17
Входные данные
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
Примечание

Для первого примера все задания должны быть выполнены, чтобы произошла забавная сценка.

Первоначально время равно $$$0$$$. Ничего не происходит до момента времени $$$3$$$, когда Окабэ понимает, что он должен был выполнить $$$2$$$-ю задачу в момент времени $$$2$$$. Затем он перемещается во времени в момент времени $$$2$$$ и выполняет задание.

Поскольку задание уже выполнено, он не перемещается во времени снова, когда время снова становится $$$3$$$. Однако в момент времени $$$4$$$ он перемещается в момент времени $$$1$$$, чтобы выполнить $$$1$$$-е задание.

Это отменяет $$$2$$$-е задание. Это означает, что задание $$$2$$$ на данный момент не выполнено, а значит, смешная сцена не произойдет в этот момент, несмотря на то что задание $$$1$$$ на данный момент выполнено, и Окабэ ранее выполнял задачу $$$2$$$.

Когда снова наступит время $$$3$$$, он снова вернется во время $$$2$$$ и снова выполнит $$$2$$$-е задание.

Теперь все задания выполнены, а Окабэ успел переместиться во времени $$$3$$$ раза.

Во втором примере Окабэ предстоит выполнить те же задания. Однако на этот раз для того, чтобы произошла забавная сцена, необходимо выполнить только первое задание. Прочитав приведенный выше пример, вы можете увидеть, что это произойдет, как только Окабэ переместится во времени в момент $$$2$$$.