Meeting Room Optimization

This problem is adapted from T2 "회의실 2" of the 2023 IOI Korea selection contest.

There are N meetings (numbered from 0 to N-1) in KDH company. The i-th meeting starts at time S[i] and ends at time E[i]. Two meetings on the same day are said to be related if either:

• They have an overlapping time interval (i.e. their time intervals intersect in a nonempty interval – note that if one meeting ends exactly when another begins, they do not overlap), or
• There exists a third meeting with which both are related (this relation is transitive).

If two meetings are not related they are called unrelated. In scheduling the meetings into rooms on a given day, KDH must assign meetings to rooms such that no two unrelated meetings are assigned to the same room. The cost of a meeting day is defined as the minimum number of meeting rooms required by such an assignment.

Currently, KDH holds all N meetings in a day. They now plan to cancel meetings one‐by‐one over N-1 days until only one meeting is left. More precisely, on each day they:

• Select one meeting that has not yet been cancelled.
• Cancel it permanently starting that day.
• Conduct all the remaining (not‐cancelled) meetings, incurring a cost as defined above.

KDH wants to choose the order in which meetings are cancelled so that the total cost over the N-1 days is minimized. Your task is to compute the number of cancellation schedules that achieve this minimum total cost. Two schedules are considered the same if the sequence of meetings cancelled over the N-1 days is identical. Since the answer can be large, output it modulo 1000000007.

Mathematical formulation:

Let the relation of overlapping be defined as
\( i \sim j \quad \text{if} \quad [S[i],E[i]) \cap [S[j],E[j]) \neq \emptyset \).
Define the transitive closure of \(\sim\) as the relation of being related. Thus, the meetings can be partitioned into connected components (when sorted by S) such that meetings in the same component are related, and meetings in different components are not.
It turns out that if one cancels meetings in each connected component in a way that at every step the remaining meetings in that component form a consecutive block (with respect to the sorted order by start time), then the cost for that component is minimized. In such a block of k meetings, one may only cancel an endpoint meeting (either the first or the last) in order to preserve contiguity. Therefore, there are exactly \(2^{k-1}\) ways to cancel the meetings inside the component if one meeting is ultimately allowed to survive, and exactly \(2^{k-1}\) ways if the entire component is cancelled. Overall, one is forced (in an optimal schedule) to cancel all meetings in all but one component as early as possible while delaying the cancellations in the surviving component. A combinatorial analysis shows that if the initial meeting set splits into r connected components with sizes \(c_1, c_2, \dots, c_r\) (with \(\sum_{i=1}^{r}c_i=N\)), then the number of optimal schedules is given by

[ \text{answer} = \frac{(N-1)! \cdot 2^{N-r} \cdot N}{\prod_{i=1}^{r} (c_i)!} \quad (\bmod; 10^9+7). ]

Your task is to implement the function count_removals(S, E) which receives two integer arrays of length N and returns the number of cancellation orders achieving the minimum total cost modulo 1000000007.

inputFormat

The function count_removals receives two parameters:

• S: an integer array of size N representing the start times of the meetings.
• E: an integer array of size N representing the end times of the meetings.

You may assume that N ≥ 1 and that if E[i] == S[j] then the meetings do not overlap.

outputFormat

The function should return an integer, which is the number of cancellation orders that achieve the minimum total cost, taken modulo 1000000007.

sample

3
1 2 3
4 5 6

4