TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

94.7% (36/38)

Submission's AC Ratio

50.7% (70/138)

Tags

Description

在一百年後的未來,你培育出了一種帶有無限繁殖基因的兔子。你決定帶著一隻能夠自體繁殖的新生兔子到月球上,成為世界最大的兔子農!

你培養出的這種兔子十分特別,每一隻兔子在新生後的兩個月會完全的發育,接著從第三個月開始每個月都會固定繁殖出一隻新生的兔子。於是你抵達月球的第一個月有一隻新生的兔子 A ,第二個月還是只有兔子 A ,在第三個月兔子 A 會繁殖出一隻新生的兔子 B ,所以總共會有兩隻兔子。第四個月兔子 A 繼續繁殖出兔子 C ,總共會有三隻兔子。第五個月兔子 A, B各會繁殖出一隻兔子,總共有五隻兔子。以此類推,你的兔子農場很快的就充滿著兔子,不過因為你在月球上有用不完的空地,所以不必擔心空間的問題。

而為了成為偉大的兔子農,你會在每個月紀錄每隻兔子間的互動,以供未來的你進一步的研究。正式來說,如果你在第 $k$ 個月有 $M_k$ 隻兔子,那這個月你就會記錄下 $\frac{M_k\times (M_k-1)}{2}$(也就是${M_k}\choose {2}$,或是 $C^ {M_k}_{2}$ )筆資料。由於一百年後的未來一樣是雲端大數據時代,你把所有的資料都存放在地球上的資料庫中。而你知道地球上的資源有限,也許哪天就沒有地方存放你珍貴的資料了。所以你想要預先計算出你在某個時段內總共會紀錄的資料筆數。由於數字可能很大,請輸出資料筆數除以$10^ 9+7$後的餘數。

Input Format

測試資料第一行有一個整數 $N$ ,代表你關注的時段數量。

接下來有 $N$ 行,其中第 $i $行包含兩個以空白隔開的整數 $s_i, t_i$ ,表示第 $i$ 個時段是從第 $s_i$個月到第 $t_i$ 個月。

  • $1\leq N\leq 10^ 4$
  • $1\leq s_t\leq t_i \leq 10^ {18}$

Output Format

請輸出 $N$ 行,其中第 $i$ 行包含一個整數表示第 $i$ 個時段內資料筆數除以 $10^ 9 + 7$ 的餘數。

Sample Input 1

5
1 1
2 2
3 3
4 4
1 5

Sample Output 1

0
0
1
3
14

Hints

Problem Source

2016 NPSC高中組決賽

Subtasks

No. Testdata Range Score
1 0~1 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 262144 1
1 3000 262144 262144 1