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$$$ 次,就会发生这种情况。