17440번 - 코포빵 토너먼트

전 세계 초 인싸 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 ≤ N ≤ 100,000)

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

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

또한, 10⁹+7로 나누어떨어지지 않는 임의의 정수 X에 대해, XY ≡ 1 (mod 10⁹+7) 이고 1 ≤ Y < 10⁹+7인 정수 Y가 유일하게 존재한다. 그런 Y를 X^-1이라 하자.

N개의 줄에 걸쳐 i번째 줄에는 i회 대회에 대한 기댓값을 나타내는 정수 P_i, Q_i에 대해 P_iQ_i^-1을 10⁹+7로 나눈 나머지를 출력한다.

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

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