f013.
N項的費氏數列
內容
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後再輸出。」
輸入說明
第一行有一個整數t(1≤t≤10000)
接下來t行每行有兩個數字n,k(2≤n≤30,1≤k≤2^50)
代表要求n項的費氏數列的第k項
輸出說明
請把答案%1000000007再輸出
範例輸入
#1
5 2 5 3 2 10 12 25 1000 30 1125899906842624
範例輸出
#1
5 1 19 637354692 966611599
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (33%): 0.5s , <1M
公開 測資點#1 (33%): 5.0s , <1M
公開 測資點#2 (34%): 10.0s , <1M
公開 測資點#0 (33%): 0.5s , <1M
公開 測資點#1 (33%): 5.0s , <1M
公開 測資點#2 (34%): 10.0s , <1M
提示 ：
有時認為比較快的方法，反而比較慢；
有時認為比較慢的方法，反而比較快。
若題敘、測資有誤，歡迎提出
不要作弊············
-----------------
100%：無特別限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||