Radek과 친구들의 회사 사장인 Radek은 경쟁사인 Mati와 회사에 있는 모든 문서 선반을 물에 잠기게 하려고 합니다. 완벽한 사보타주를 위해 그는 친구이자 배관공인 Janusz에게 각 선반 위에 작은 수도꼭지를 설치해 달라고 부탁했습니다.

Mati와 회사의 선반은 평면 위의 선분으로 단순화하여 나타낼 수 있습니다. 각 선반은 어떤 두 점 $(l_i, h_i)$와 $(r_i, h_i)$ 사이의 선분입니다. 배관공이 설치한 수도꼭지는 좌표 $(\frac{l_i+r_i}{2}, h_i + 0.5)$에 위치합니다. 이 방의 바닥은 $OX$ 축으로 나타냅니다.

$i$번째 선반 위의 수도꼭지를 틀면 해당 선반이 물에 잠깁니다. 자연스러운 결과로, 물은 선반의 끝에서 수직으로 아래로 떨어지기 시작하며, 아래에 있는 다른 선반들을 잠기게 하거나 자연 배수 시스템을 통해 바닥으로 떨어집니다.

두 번째 예제 테스트에서 수도꼭지 하나를 틀었을 때 물이 흐르는 모습.

Radek은 정해진 순서대로 수도꼭지를 고려할 것입니다. $i$번째 수도꼭지를 고려하는 순간, 그는 $i$번째 선반이 아직 물에 잠기지 않은 경우에만 수도꼭지를 틉니다.

Radek은 아직 수도꼭지를 고려할 순서를 정하지 않았습니다. 그는 $n!$개의 순서 중 하나를 동일한 확률로 무작위로 선택할 것입니다. Radek은 이제 평균적으로 몇 개의 수도꼭지를 틀어야 하는지 알고 싶어 합니다.

당신의 임무는 Radek의 질문에 답하고 그 결과를 $10^9 + 7$로 나눈 나머지를 출력하는 것입니다. 형식적으로, 결과가 $p/q$이고 $q \neq 0$, $\gcd(p, q) = 1$이라고 할 때, $p \cdot q^{-1} \pmod{10^9 + 7}$을 출력해야 합니다. 여기서 $q^{-1}$은 $q \cdot q^{-1} \equiv 1 \pmod{10^9 + 7}$을 만족하는 $\{1, 2, \dots, 10^9 + 6\}$ 집합의 유일한 수입니다.

문제의 조건을 만족하는 모든 테스트 케이스에 대해 결과는 유리수이며, 기약 분수 형태의 분모는 $10^9 + 7$로 나누어떨어지지 않음이 증명되어 있습니다.

입력

입력의 첫 번째 줄에는 Mati 회사에 있는 선반의 개수를 나타내는 자연수 $n$ ($1 \le n \le 500\,000$)이 주어집니다.

다음 $n$개의 줄에는 선반에 대한 설명이 주어집니다. 이 중 $i$번째 줄에는 문제에서 설명한 두 자연수 $l_i, r_i$ ($1 \le l_i < r_i \le 2 \cdot n$)가 주어집니다. 단순화를 위해 $h_i = i$라고 가정합니다.

모든 수 $l_i, r_i$는 서로 다르며, $l_i, r_i$는 $1$부터 $2 \cdot n$까지의 수에 대한 순열을 이룬다고 가정할 수 있습니다.

출력

표준 출력의 유일한 줄에 Radek이 틀어야 할 평균 수도꼭지 개수를 $10^9 + 7$로 나눈 나머지를 출력합니다.

예제

입력 1

3
4 6
1 3
2 5

출력 1

2

입력 2

5
2 9
3 4
1 8
6 10
5 7

출력 2

233333338

참고

예제 설명: 첫 번째 예제 테스트에서 Radek이 수도꼭지를 고려할 수 있는 모든 가능한 순서를 고려해 봅시다.

• 순서 1, 2, 3의 경우, 그는 3개의 수도꼭지를 모두 틉니다.
• 순서 1, 3, 2의 경우, 그는 첫 번째와 세 번째 수도꼭지를 틉니다. 세 번째 수도꼭지를 튼 후 물이 두 번째 선반도 잠기게 하므로, 두 번째 수도꼭지는 틀 필요가 없습니다.
• 순서 2, 1, 3의 경우, 그는 3개의 수도꼭지를 모두 틉니다.
• 순서 2, 3, 1의 경우, 그는 두 번째와 세 번째 수도꼭지를 틉니다. 세 번째 수도꼭지를 튼 후 물이 첫 번째 선반을 잠기게 하므로, 첫 번째 수도꼭지는 틀 필요가 없습니다.
• 순서 3, 1, 2 및 3, 2, 1의 경우, 그는 세 번째 수도꼭지만 틉니다. 이를 튼 후 모든 선반이 잠기게 되므로, 다른 수도꼭지를 틀 필요가 없습니다.

따라서 Radek은 평균적으로 $\frac{1}{6} \cdot (3 + 2 + 3 + 2 + 1 + 1) = 2$개의 수도꼭지를 틀어야 합니다.

두 번째 예제 테스트에서 Radek은 평균적으로 $\frac{91}{30}$개의 수도꼭지를 틀어야 합니다. $30^{-1} \equiv 233333335 \pmod{10^9 + 7}$이므로, $91 \cdot 233333335 \equiv 21233333485 \equiv 233333338 \pmod{10^9 + 7}$입니다.