KDH 公司每天进行 $N$ 场会议。会议编号从 $0$ 到 $N-1$，对于所有 $0 \le i \le N-1$，第 $i$ 场会议在时刻 $S[i]$ 开始，在时刻 $E[i]$ 结束。

KDH 公司举办会议的方式很特别。在某一天进行的任意两场不同会议 $i$ 和 $j$，如果满足以下至少一个条件，则称这两场会议在当天是“相关”的：

• 存在两场会议同时进行的时刻。
• 存在当天进行的会议 $k$，使得会议 $i$ 和 $k$ 相关，且会议 $j$ 和 $k$ 相关。

如果两场会议 $i$ 和 $j$ 不是相关会议，则称这两场会议在当天是“不相关”的。

KDH 公司每天进行会议时，会将每场会议分配到特定的会议室进行。此时，当天互不相关的会议不能被分配到同一个会议室。在满足这些条件的分配方法中，KDH 公司会选择所需会议室数量最少的方法。我们将这种分配方案中所需的最小会议室数量称为会议的“成本”。

KDH 公司认为目前会议消耗了过多不必要的资源，因此决定将会议数量减少到仅剩一场。为此，KDH 公司在 $N-1$ 天内，每天重复以下操作：

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

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

为了进一步降低成本，KDH 公司希望在多种方案中选择一种，使得 $N-1$ 天内每天所需成本之和最小。你需要为 KDH 公司计算存在多少种这样的方案。两种方案相同是指：每天选择取消的会议都完全相同。具体来说，如果 $N-1$ 天内每天选择取消的会议都相同，即使会议室中剩余会议的分配方式不同，也被视为同一种情况。由于方案数量可能非常大，请计算其对 $1\,000\,000\,007$ 取模后的结果。

实现细节

你需要实现以下函数：

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

• $S, E$: 大小为 $N$ 的整数数组。对于所有 $0 \le i \le N-1$，第 $i$ 场会议在时刻 $S[i]$ 开始，在时刻 $E[i]$ 结束。
• 该函数应返回在 $N-1$ 天内使每天所需成本之和最小的方案数，结果对 $1\,000\,000\,007$ 取模。

提交的源代码中不得执行任何输入输出函数。

数据范围

• $2 \le N \le 2\,000$
• 对于所有 $0 \le i \le N-1$，$1 \le S[i] < E[i] \le 2N$
• 对于所有 $0 \le i < j \le 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 \le 10$，$S[0] = 1, E[0] = 2N$
2. (8分) $N \le 20$
3. (30分) $N \le 300$
4. (12分) 同一时刻进行的会议最多有 2 场。
5. (12分) 对于所有 $0 \le i, j \le N-1$（$i \neq j$），不存在满足 $S[i] < S[j] < E[i] < E[j]$ 的 $i, j$ 对。
6. (10分) 对于所有 $0 \le i, j \le N-1$（$i \neq j$），不存在满足 $S[i] < S[j] < E[j] < E[i]$ 的 $i, j$ 对。
7. (25分) 无额外限制。

样例

样例 1

输入： $N = 4, S = [1, 3, 5, 7], E = [2, 4, 6, 8]$

调用：

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

输出： 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

Sample grader

Sample grader 接收以下格式的输入：

• 第 1 行：$N$
• 第 $2+i$ 行（$0 \le i \le N-1$）：$S[i] \ E[i]$

Sample grader 输出：

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

请注意，Sample grader 可能与实际评测中使用的 grader 不同。