회의실 2

기업 KDH에서는 $N$개의 회의를 매일 진행한다. 회의에는 0부터 $N - 1$까지의 번호가 붙어 있다. 모든 $0 \le i \le N - 1$에 대해 $i$번 회의는 시각 $S[i]$에 시작해 시각 $E[i]$에 끝난다.

KDH는 회의를 특별한 방식으로 연다. 어떤 날에 진행되는 서로 다른 회의 $i$와 $j$가 다음 조건 중 하나 이상을 만족하면, 두 회의는 그 날 서로 관련있는 회의라고 부른다.

• 두 회의가 동시에 진행되는 시각이 존재한다.
• 그 날 진행되는 회의 $k$가 존재하고, $k$는 $i$와 $j$ 모두와 관련있다.

두 회의 $i$와 $j$가 서로 관련있는 회의가 아니면, 두 회의는 그 날 서로 관련없는 회의라고 부른다.

KDH는 매일 회의를 진행할 때 각 회의를 특정 회의실에 배정한다. 그 날 서로 관련없는 회의는 같은 회의실에 배정되지 않아야 한다. KDH는 이 조건을 만족하는 배정 가운데 필요한 회의실 수가 가장 적은 방법을 선택한다. 이러한 배정에서 필요한 최소 회의실 수를 회의들의 비용이라고 한다.

KDH는 회의에 불필요하게 많은 자원이 쓰인다고 판단해 회의 수를 하나로 줄이기로 했다. 이를 위해 KDH는 $N - 1$일에 걸쳐 매일 다음 작업을 반복한다.

• 아직 취소하지 않은 회의 하나를 선택한다.
• 그 날부터 선택한 회의를 영구적으로 취소한다.
• 취소되지 않은 회의를 전부 진행한다.

이 과정이 끝나면 한 회의를 제외한 모든 회의가 취소된다. 마지막에 남는 회의가 무엇인지는 상관없다.

KDH는 비용을 더 줄이기 위해 $N - 1$일 동안 매일 발생하는 비용의 합이 최소인 방법을 고르려고 한다. 이러한 방법이 몇 가지인지 구해야 한다. 두 방법이 같다는 것은 각 날에 취소하기로 선택한 회의들이 모두 같다는 뜻이다. 구체적으로, $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]$