题目背景

请勿用 C++14 (GCC 9) 提交。

请在代码开头加入如下代码：

#include<vector>
int count_removals(std::vector<int> S, std::vector<int> E);

题目描述

题目译自 2023년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2 「회의실 2」

KDH 公司每天会举行 $N$ 场会议。每场会议都有一个编号，从 $0$ 到 $N-1$。对于每个 $i$ $(0 \leq i \leq N-1)$，第 $i$ 场会议在时间 $S[i]$ 开始，在时间 $E[i]$ 结束。

KDH 公司安排会议的方式很特别。如果某一天进行的两场不同会议 $i$ 和 $j$ 满足以下条件之一，则称这两场会议在该天是相关的：

• 两场会议有重叠的时间段。
• 存在第三场会议 $k$，使得 $i$ 和 $j$ 都与 $k$ 相关。

如果两场会议 $i$ 和 $j$ 在该天不是相关的，则称它们在该天是无关的。KDH 公司在安排会议时，会将每场会议分配到特定的会议室。要求在同一天内，无关的会议不能分配到同一个会议室。KDH 公司会选择满足这些条件的分配方案中所需会议室数量最少的方案。所需的最少会议室数量称为会议的成本。

KDH 公司认为目前的会议安排浪费了太多资源，决定将会议数量减少到只剩一场。为此，KDH 公司将在 $N-1$ 天内每天进行以下操作：

• 选择一个尚未取消的会议。
• 从当天起永久取消该会议。
• 进行所有未取消的会议。

当这个过程结束时，除了最后一场会议外，所有会议都被取消。最后剩下的会议是哪一场并不重要。

为了进一步节省成本，KDH 公司希望找到一种方法，使得在 $N-1$ 天内每天的总成本最小。你需要计算出有多少种方法可以实现这一目标。两种方法相同的定义是：在 $N-1$ 天内每天选择取消的会议完全相同。即使剩下的会议分配方式不同，只要每天取消的会议相同，就认为是相同的方法。由于方法数量可能非常大，结果需要对 $1000000007$ 取模。

你需要实现以下函数：

int count_removals(vector<int> S, vector<int> E);

• S, E：大小为 $N$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-1)$，第 $i$ 场会议在时间 $S[i]$ 开始，在时间 $E[i]$ 结束。
• 该函数返回在 $N-1$ 天内每天的总成本最小的情况下，选择取消会议的方法数量，对 $1000000007$ 取模。

注意，提交的代码中不应包含任何输入输出操作。

输入格式

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2+i$ $(0 \leq i \leq N-1)$ 行：$S[i]\,E[i]$

输出格式

示例评测程序按以下格式输出：

• 第 $1$ 行：函数 count_removals 返回的值

4
1 2
3 4
5 6
7 8

24

10
1 5
2 3
4 7
6 11
8 9
10 15
12 13
14 20
16 17
18 19

13280

10
1 20
2 9
3 4
5 8
6 7
10 17
11 16
12 13
14 15
18 19

845040

10
1 5
2 9
3 10
4 12
6 14
7 16
8 17
11 18
13 19
15 20

1797408

10
12 16
5 7
10 19
2 3
4 6
17 20
8 11
1 15
14 18
9 13

647760

提示

样例 1 解释

考虑 $N=4, S=[1,3,5,7], E=[2,4,6,8]$ 的情况。

评测程序将调用如下函数：

count_removals([1,3,5,7], [2,4,6,8]);

无论选择哪种方式取消会议，每天所需的会议室数量（即成本）依次为 $3$、$2$、$1$，总成本为 $6$。因此，所有方法都是可行的。

函数应返回 24。

数据范围

对于所有输入数据，满足：

• $2 \leq N \leq 2000$
• 对于每个 $i$ $(0 \leq i \leq N-1)$，$1 \leq S[i] < E[i] \leq 2N$
• 对于每个 $i,j$ $(0 \leq i < j \leq N-1)$，$S[i] \neq S[j], S[i] \neq E[j], E[i] \neq S[j], E[i] \neq E[j]$

详细子任务附加限制及分值如下表所示。