코포빵 토너먼트

전 세계 초 인싸 PS 동아리 SNUPS는 매년 전 세계의 Codeforces 랭커들이 모여들어 코포빵 대결을 하며 실력을 뽐내는 코포빵 토너먼트 대회를 개최한다.

코포빵 토너먼트를 개최하려면 먼저 Codeforces 레이팅의 구간 $[A, B]$를 정해야 한다. 그러면 레이팅이 그 구간에 속하고 모두 서로 다른 레이팅을 가진 $B-A+1$명을 선발해 대회를 진행한다. 그럼 $[A, B]$ 구간의 코포빵 토너먼트가 어떻게 진행되는지 살펴보자.

먼저 $B-A+1$명의 참가자를 임의의 순서로 한 줄에 세운다. 가능한 모든 순서가 선택될 확률은 같다. 그다음 줄에 1명이 남을 때까지 다음 과정을 반복한다.

• 줄의 앞에서부터 두 명씩 짝지은 뒤, 동시에 코포빵 대결을 한다.
• 각 대결에서 진 사람(들)이 줄에서 빠진다.
• 단, 줄에 홀수 명이 서 있었으면, 마지막 사람은 경기에 참여하지 않고 줄에 남는다.

코포빵 대결의 결과는 두 선수의 Codeforces 레이팅에 의해서만 결정된다. 즉, 레이팅이 서로 다른 두 사람이 대결하면 레이팅이 큰 사람이 무조건 이긴다.

동현이는 올해로 $N+1$회를 맞은 코포빵 토너먼트에서 '기록자'를 맡게 되었다. 기록자는 매 대결이 이루어질 때마다 승자의 Codeforces 레이팅을 대진표에 적는 역할을 맡는다. 기록자가 적는 수의 개수는 항상 $B-A$개로 일정하지만, 적는 숫자의 개수는 처음에 참가자들이 어떤 순서로 줄을 서느냐에 따라 달라질 수 있다.

동현이는 예전 기록을 찾아보던 중, 1회부터 $N$회 대회까지에 해당하는 Codeforces 레이팅 구간이 모두 적힌 종이를 발견했다. 이 종이를 읽던 동현이는 1회부터 $N$회까지 각 대회에서 기록자가 적었을 숫자의 개수가 궁금해졌다. 전체 대진표는 남아 있지 않아 정확히는 알 수 없지만, 참가자들을 모든 가능한 순서가 선택될 확률이 동일하도록 임의의 순서로 세웠다고 할 때 적었을 숫자 개수의 기댓값은 구할 수 있다.

동현이의 궁금증을 해결해 주자!

첫 줄에 지금까지 열렸던 대회의 수 $N$이 주어진다. ($1 \le N \le 100{,}000$)

다음 $N$개의 줄에 걸쳐 $i$회 대회에 해당하는 참가자 Codeforces 레이팅 구간을 나타내는 두 정수 $A_i$, $B_i$가 주어진다. ($1 \le A_i \le B_i \le 9{,}999{,}999$)

$i$회 대회에서 참가자들을 모든 가능한 순서가 선택될 확률이 동일하도록 임의의 순서로 세웠다고 할 때, 그 대회의 기록자가 적었을 숫자 개수의 기댓값은 $\frac{P_i}{Q_i}$ 꼴로 유일하게 표현된다. 여기서 $P_i$, $Q_i$는 서로소인 0 이상의 정수이고, $Q_i$는 $10^9+7$로 나누어떨어지지 않는다.

$10^9+7$로 나누어떨어지지 않는 임의의 정수 $X$에 대해, $XY \equiv 1 \pmod{10^9+7}$ 이고 $1 \le Y < 10^9+7$인 정수 $Y$가 유일하게 존재한다. 그런 $Y$를 $X^{-1}$이라 하자.

$N$개의 줄에 걸쳐 $i$번째 줄에는 $P_i Q_i^{-1}$을 $10^9+7$로 나눈 나머지를 출력한다.

1회 대회에서는 모든 참가자의 레이팅이 한 자리 수였으므로 무조건 4개의 숫자를 적었을 것이다.

2회 대회에서는 레이팅이 10인 사람이 부전승했던 경우와 그렇지 않았던 경우로 나누어 생각해 보면 기댓값이 $\frac{1}{3} \times 3 + \frac{2}{3} \times 4 = \frac{11}{3}$ 임을 알 수 있다.