f013: N項的費氏數列
Tags : 數學 費氏數列
Accepted rate : 7人/18人 ( 39% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-05-10 20:28

Content

Leonardo Pisano Bigollo 1175~1250

Caido:「這位是費波那契,是西方第一個研究費波那契數列的人。」

caido:「你是說第一項和第二項是1,第k項是第k-1項加第k-2項的數列嗎?」

Caido:「對,不過我們現在要把2項的費式數列變成n項的費氏數列,數列的前n項是1,第k項是第k-n項到第k-1項的總和。」

caido:「聽起來滿簡單的啊。」

Caido:「嗯,不過因為數字可能會很大,所以答案要%1000000007後再輸出。」

Input

第一行有一個整數t(1≤t≤10000)

接下來t行每行有兩個數字n,k(2≤n≤30,1≤k≤2^50)

代表要求n項的費氏數列的第k項

Output

請把答案%1000000007再輸出

Sample Input #1
5
2 5
3 2
10 12
25 1000
30 1125899906842624
Sample Output #1
5
1
19
637354692
966611599
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (33%): 0.5s , <1M
公開 測資點#1 (33%): 5.0s , <1M
公開 測資點#2 (34%): 10.0s , <1M
Hint :

有時認為比較快的方法,反而比較慢;

有時認為比較慢的方法,反而比較快。

若題敘、測資有誤,歡迎提出

不要作弊············

Tags:
數學 費氏數列
出處:
Caido第二屆簡單的小競賽 [管理者:
becaido (Caido)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」