費式數列相信大家應該都略有耳聞
在要求的項數非常小的時候，我們可以很輕鬆的算出來
可是當我要連續問好幾個很大的項數呢？
一般來說，我們會先寫最簡單的寫法：$ fib_{n} = fib_{n-1} + fib_{n-2} $
但是這種寫法在每次的詢問都從 $n$ 開始往下算到直到終止條件 $fib_{1}$, $fib_{2}$為止
會非常浪費時間
發現太浪費時間以後，我們換個方法來優化
我們可以用很大的記憶體來把算過的都記起來
可惜的事，這樣還是會太慢（試想 n 是 2147483647 的時候）
在上面講的這兩種方法都是對的，只可惜速度差了點
因此，為了處理這次的問題
我們要教大家一個有趣的東西 - 矩陣快速冪
或許你心中會有個疑問，費式數列跟矩陣能扯上什麼關係？
我們把費式數列改寫一下：
$\begin{bmatrix} fib_{n+1} \\ fib_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} fib_{n-1} \\ fib_{n-2} \end{bmatrix}$
這樣是不是就能看到矩陣的性質出來了呢？
透過展開與矩陣的性質，我們可以再次改寫費式數列：
$\begin{bmatrix} fib_{n+1} \\ fib_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^ {n} \times \begin{bmatrix} 1 \\ 0 \end{bmatrix}$
很明顯的可以發現，現在我們的程式變成是只要連乘 $n$ 次的 $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ 就可以得到答案了！
事實上，如果遇到 $n$ 是 2147483647這麼大的話，連乘這麼多次還是不夠快。
因此，這時候就要來介紹我們的好朋友 - 快速冪
對一個 32-bit 的整數，我們可以用 bit map 的方式表現它
$0 => 00000000 00000000 00000000 00000000$
$1 => 00000000 00000000 00000000 00000001$
$2147483647 => 01111111 11111111 11111111 11111111$
這時候我們如果要算以下這個式子可以這樣算
$x^{n}, n = 87$
$87 => 00000000 00000000 00000000 01010111$
對 $87$ 而言，第 $0, 1, 2, 4, 6$ 個 bit 是 $1$
再次轉換一下這個方程式：
$x^{87} = 1 \times x^{2^{0}} \times x^{2^{1}} \times x^{2^{2}} \times x^{2^{4}} \times x^{2^{6}}$
因此可以推導出一個結論：
從第零個 bit 開始往前掃，如果該 bit 是 $1$ 就把當前的 $x$ 乘進去答案裡，接著再把 $x$ 平方，繼續到最後一個 bit，最後我們就能得到答案了。
說明到此結束，本題希望大家能實作這個矩陣快速冪來求出費式數列。
下面這個程式碼是再算普通次方版本的快速冪寫法，希望能幫助你理解快速冪的概念：
有多筆測試資料，每一行為一筆測資
每筆測資只會有一個數字 $n (1 <= n < 2^{31})$，代表要求 $fib(n)$
注意，因為數字可能會非常非常巨大
請千萬不要忘記把答案取 $mod$ $100000007$ 噢！