費波那契數列


Submit solution

Points: 100 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

請找出第 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

There are no comments at the moment.