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

子題配分