Problem Description

Author: louishuang

費波那契數（義大利語：Numero di Fibonacci），又譯為菲波拿契數、菲波那西數、斐氏數、黃金分割數、費氏數列。所形成的數列稱為費波那契數列（義大利語：Successione di Fibonacci），又譯為菲波拿契數列、菲波那西數列、斐氏數列、黃金分割數列、費氏數列。這個數列是由義大利數學家費波那契在他的《算盤書》中提出。

在數學上，費波那契數是以遞迴的方法來定義：

• 

• 

• （）

用白話文來說，就是費氏數列由0和1開始，之後的費波那契數就是由之前的兩數相加而得出。首幾個費波那契數是：

1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89、 144、 233、 377、 610、 987……（OEIS數列A000045）

特別指出：0 不是第一項，而是第零項（）。

謝謝維基百科讓我複製題敘

Input Format

輸入的第一行包含一個正整數 $T$，代表接下來有 $T$ 筆詢問。

接下來的 $T$ 行，每行包含一個非負整數 $N$。

Output Format

對於每筆詢問，請輸出一行包含一個整數，代表 $F_N \pmod{10^9 + 7}$ 的值。

3
10
0
1

55
0
1

Hint

$\mathbf{30}$%：$1 \le T \le 10$ 且 $0 \le N \le 30$

$\mathbf{30}$%：$1 \le T \le 10$ 且 $0 \le N \le 10^6$

$\mathbf{40}$%：$1 \le T \le 10^5$ 且 $0 \le N \le 10^{18}$