費波那契數列
請找出第 n 項的費波那契數列 \( F_n\) 對 \( 10^9+7\) 取模後的數字。費波那契數列定義如下:
\( F_0=0\)
\( F_1=1\)
\( F_i = F_{i-1}+F_{i-2}\)
此題有多筆測資
輸入格式
第一行有一個數字 \( T\) (\( 1 \le T \le 100\,000\) ) 代表測資數量。接下來 \( T\) 行每行有一個數字 \( n\) ,代表要詢問的是\( F_n\) 對 \( 10^9+7\) 取模後的數字。
輸出格式
一個答案一行,輸出 \(T \) 行。
範例輸入
5
0
1
10
1000000
1000000000000000000
範例輸出
0
1
55
918091266
209783453
子題配分
編號 | 範圍 | 分數 | 前置條件 |
---|---|---|---|
1 | \( 0 \le n \le 10 \) | 10 | 無 |
2 | \( 0 \le n \le 10^6 \) | 30 | 子題 1 |
3 | \( 0 \le n \le 10^{18} \) | 60 | 子題 1,2 |
Comments