회의실 2

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

KDH에서 회의를 여는 방식은 특별하다. 어떤 날에 진행되는 서로 다른 회의 $i$ 와 $j$ 가 다음 조건 중 적어도 하나를 만족하면 두 회의는 해당 날에 서로 관련있는 회의라고 부른다:

두 회의가 동시에 진행되는 시각이 존재한다.
두 회의와 동시에 관련있는 해당 날에 진행되는 회의 $k$ 가 존재한다.

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

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

KDH는 현재 회의들에 불필요하게 많은 자원이 소모된다고 판단해 회의의 수를 단 하나로 줄이기로 결정하였다. 이를 위해, KDH는 $N - 1$ 일에 걸쳐 매일 다음과 같은 작업을 반복한다:

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

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

KDH는 더욱 비용을 절감하기 위해 여러 방법들 중 $N - 1$ 일 동안 각 날에 필요한 비용의 합이 최소인 방법을 선택하려고 한다. 당신은 KDH를 위해 이러한 방법이 얼마나 존재하는지 구해야 한다. 두 방법이 같다는 것은, 각 날에 취소하기로 선택한 회의들이 모두 같다는 것을 뜻한다: 구체적으로, $N - 1$ 일에 걸쳐 취소하기로 선택한 회의가 모두 같을 경우, 회의실에 남은 회의들을 배정하는 방법이 다르더라도 이는 같은 경우로 간주한다. 단, 방법의 수가 매우 커질 수 있으므로 소수 $1\\,000\\,000\\,007$ 로 나눈 나머지를 구해야 한다.

문제

제한