在上次的課程上，我們學會了在O(lg P)的時間內算出BP
的方法。
但是，如果B不是一個數字，而是一個矩陣呢？還記得費式數列嗎？
Fn = Fn-1 + Fn-2 , for n > 1
F1 = 1
F0 = 0
其實費式數列可以轉乘矩陣相乘的形式，[Fn ;Fn-1 ] = [1,1;1,0]*[Fn-1 ;Fn-2 ]
我們將[Fn-1 ;Fn-2 ]再次拆開，可得到：[Fn ;Fn-1 ] = [1,1;1,0;]∗ ([1,1;1,0] [Fn-2 ;Fn-3 ]) = [1,1;1,0]2*[Fn-2 ;Fn-3 ]
所以，[Fn ;Fn-1 ] = [1,1;1,0]n−1*[F1 ;F0]
設B = [1,1;1,0] , P = n − 1，則問題轉化為Big Mod。
現在給予數字n 及M,求Fn % 2M
每行有兩個數字n, M。(n ≤ 2147483647, M ≤ 20)
每行有一個數字，代表Fn % 2M