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 個月有 Mk 隻兔子,那這個月你就會記錄下 Mk×(Mk1)2(也就是(Mk2),或是 C2Mk )筆資料。由於一百年後的未來一樣是雲端大數據時代,你把所有的資料都存放在地球上的資料庫中。而你知道地球上的資源有限,也許哪天就沒有地方存放你珍貴的資料了。所以你想要預先計算出你在某個時段內總共會紀錄的資料筆數。由於數字可能很大,請輸出資料筆數除以109+7後的餘數。

Input Format

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

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

  • 1N104
  • 1stti1018

Output Format

請輸出 N 行,其中第 i 行包含一個整數表示第 i 個時段內資料筆數除以 109+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