Meeting Room 2

The company KDH holds $N$ meetings every day. The meetings are numbered from 0 to $N - 1$. For every $0 \le i \le N - 1$, meeting $i$ starts at time $S[i]$ and ends at time $E[i]$.

KDH holds its meetings in a special way. On a given day, two different meetings $i$ and $j$ held that day are called related meetings if at least one of the following holds:

• There is a time when both meetings are in progress.
• There is a meeting $k$ held that day that is related to both $i$ and $j$.

If two meetings $i$ and $j$ are not related, they are called unrelated meetings that day.

When KDH holds meetings each day, it assigns every meeting to a specific meeting room. Unrelated meetings held that day must not be assigned to the same room. KDH chooses the assignment that satisfies this condition and uses the fewest rooms. The minimum number of rooms needed for such an assignment is called the cost of the meetings.

KDH judges that too many resources are being spent on the meetings, so it decides to reduce the number of meetings to just one. To do this, KDH repeats the following steps on each of the $N - 1$ days:

• Choose one meeting that has not been canceled yet.
• From that day on, permanently cancel the chosen meeting.
• Hold all meetings that have not been canceled.

After this process ends, every meeting except one has been canceled. It does not matter which meeting remains at the end.

To reduce costs further, KDH wants to choose a method whose sum of costs over the $N - 1$ days is minimal. Find the number of such methods. Two methods are the same if the meetings chosen for cancellation are the same on every day. More precisely, if the meetings canceled over the $N - 1$ days are identical, the methods are treated as the same even if the room assignments for the remaining meetings differ. Since the count can become very large, output it modulo the prime $1\,000\,000\,007$.

• $2 \le N \le 2\,000$
• For every $0 \le i \le N - 1$, $1 \le S[i] < E[i] \le 2N$
• For every $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]$