注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "meeting2.h"。

题目描述

题目译自 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=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

考虑 $N=10, S=[1,2,4,6,8,10,12,14,16,18], E=[5,3,7,11,9,15,13,20,17,19]$ 的情况。

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

count_removals([1,2,4,6,8,10,12,14,16,18], [5,3,7,11,9,15,13,20,17,19]);

下图展示了每场会议的时间安排。

函数应返回 13280。

样例 3

考虑 $N=10, S=[1,2,3,5,6,10,11,12,14,18], E=[20,9,4,8,7,17,16,13,15,19]$ 的情况。

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

count_removals([1,2,3,5,6,10,11,12,14,18], [20,9,4,8,7,17,16,13,15,19]);

下图展示了每场会议的时间安排。

函数应返回 845040。

样例 4

考虑 $N=10, S=[1,2,3,4,6,7,8,11,13,15], E=[5,9,10,12,14,16,17,18,19,20]$ 的情况。

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

count_removals([1,2,3,4,6,7,8,11,13,15], [5,9,10,12,14,16,17,18,19,20]);

下图展示了每场会议的时间安排。

函数应返回 1797408。

样例 5

考虑 $N=10, S=[12,5,10,2,4,17,8,1,14,9], E=[16,7,19,3,6,20,11,15,18,13]$ 的情况。

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

count_removals([12,5,10,2,4,17,8,1,14,9], [16,7,19,3,6,20,11,15,18,13]);

下图展示了每场会议的时间安排。

函数应返回 647760。

数据范围与提示

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

• $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]$

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

子任务	分值	附加限制
$1$	$3$	$N \leq 10$；$S[0]=1, E[0]=2N$
$2$	$8$	$N \leq 20$
$3$	$30$	$N \leq 300$
$4$	$12$	任意时刻进行的会议最多为 $2$ 场
$5$	$12$	对于每个 $i,j$ $(0 \leq i, j \leq N-1)$，不存在 $i \neq j, S[i] < S[j] < E[i] < E[j]$ 的 $i, j$ 对
$6$	$10$	对于每个 $i,j$ $(0 \leq i, j \leq N-1)$，不存在 $i \neq j, S[i] < S[j] < E[j] < E[i]$ 的 $i, j$ 对
$7$	$25$	无附加限制

示例评测程序

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

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

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

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

示例评测程序可能与实际评测程序不同。