← 返回题目列表

Codeforces · 1583/G

G. 奥姆卡和时间旅行

中文机器翻译题面 查看原题

El Psy Kongroo。

Omkar 正在看《命运石之门》。

在《命运石之门》中,冈部伦太郎需要完成 $$$n$$$ 任务 ($$$1 \leq n \leq 2 \cdot 10^5$$$)。不幸的是,他不知道什么时候需要完成任务。

最初,时间为$$$0$$$。时间旅行现在将根据以下规则进行:

- 对于每个 $$$k = 1, 2, \ldots, n$$$,Okabe 将在 $$$b_k$$$ 时间意识到他应该在 $$$a_k$$$ ($$$a_k < b_k$$$) 时间完成第 $$$k$$$ 任务。
- 当他意识到这一点时,如果第$$$k$$$个任务已经在$$$a_k$$$时间完成,Okabe将保持通常的时间流动。否则,他会时间旅行到$$$a_k$$$时间,然后立即完成任务。
- 如果冈部时间旅行到$$$a_k$$$时间,则在此时间之后完成的所有任务将再次变得不完整。也就是说,对于每个$$$j$$$,如果$$$a_j>a_k$$$,则第$$$j$$$任务将变得不完整,如果它是完整的(如果它不完整,则什么都不会改变)。
- Okabe 记忆力很差,所以他只能在到达时间 $$$b_k$$$ 并得知他应该在时间 $$$a_k$$$ 完成第 $$$k$$$ 任务后立即穿越到时间 $$$a_k$$$。也就是说,即使 Okabe 之前已经必须执行第 $$$k$$$ 个任务,但在 $$$b_k$$$ 再次偶然发现有关此任务的信息之前,他也不会记得它。

请参阅注释以获取时间旅行的示例。

有一定的任务集合$$$s$$$,当$$$s$$$中的所有任务同时完成的第一时刻(无论当前是否有其他任务完成),就会发生一个有趣的场景。奥姆卡很喜欢这个场景,并且想知道冈部在这个场景发生之前会进行多少次时间旅行。求这个数对 $$$10^9 + 7$$$ 求模。可以证明,最终所有 $$$n$$$ 任务都会完成,因此答案总是存在。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — Okabe 需要完成的任务数。

$$$n$$$ 行如下。这些行中的第 $$$k$$$ 包含两个整数 $$$a_k$$$ 和 $$$b_k$$$ ($$$1 \leq a_k < b_k \leq 2n$$$) — 分别是 Okabe 需要完成第 $$$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$$$。

输出

输出一个整数 - Okabe 时间旅行直到集合 $$$s$$$ 中的所有任务同时完成为止的次数,以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

2
1 4
2 3
2
1 2

输出 #1

3

输入 #2

2
1 4
2 3
1
1

输出 #2

2

输入 #3

1
1 2
1
1

输出 #3

1

输入#4

6
10 12
3 7
4 6
2 9
5 8
1 11
3
2 4 6

输出#4

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

输出 #5

138

注意

对于第一个示例,需要完成所有任务才能发生有趣的场景。

最初,时间为$$$0$$$。直到 $$$3$$$ 时刻什么也没有发生,此时 Okabe 意识到他应该在 $$$2$$$ 时刻完成第 $$$2$$$ 任务。然后他穿越到时间 $$$2$$$ 并完成任务。

由于现在任务已经完成,当时间再次达到$$$3$$$时,他不会再次进行时间旅行。然而,在时间$$$4$$$,他前往时间$$$1$$$来完成$$$1$$$-st任务。

这将撤消 $$$2$$$-nd 任务。这意味着$$$2$$$-nd任务当前尚未完成,这意味着即使$$$1$$$-st任务当前已完成并且Okabe之前已完成$$$2$$$-nd任务,此时也不会发生有趣的场景。

一旦再次到了时间 $$$3$$$,他就会再次回到时间 $$$2$$$ 并再次执行 $$$2$$$-nd 任务。

现在所有任务都已完成,冈部已经旅行了 $$$3$$$ 次。

第二个样本有 Okabe 需要完成的相同任务。然而,这一次有趣的场景只需要完成第一个任务就可以发生。通过阅读上面的示例,您可以看到,一旦 Okabe 时间旅行了 $$$2$$$ 次,就会发生这种情况。