TopCoder

Thumb tan2
skylinebaby
激しい「喜び」はいらない… そのかわり深い「絶望」もない……… 「植物の心」のような人生を… そんな「平穏な生活」こそ私の目標だったのに………

User's AC Ratio

84.6% (11/13)

Submission's AC Ratio

51.2% (21/41)

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

5
1 1
2 2
3 3
4 4
1 5

Sample Output

0
0
1
3
14

Hints

Problem Source

2016 NPSC高中組決賽

Subtasks

For Testdata: 0 ~ 1, Score: 100
No. Time Limit (ms) Memory Limit (KiB)
0 3000 262144
1 3000 262144