求斐波那契第n项。

[f(n-1) f(n)] *  [0,1] = [f(n) f(n+1)]                 [1,1]

由此原理，根据矩阵乘法的结合律，用快速幂算出中间那个矩阵的n次方即可。

快速幂本质和普通快速幂一模一样，只是乘法操作换成了矩阵的乘法，可以重载。

//Stay foolish,stay hungry,stay young,stay simple#include
    
     #include
     
      using namespace std;const int MOD=1000000007;typedef long long ll;ll n;struct Mat{    ll data[3][3];    Mat(){        memset(data,0,sizeof(data));    }};Mat mut(Mat x,Mat y){    Mat ret;    for(int i=1;i<=2;i++){        for(int j=1;j<=2;j++){            for(int k=1;k<=2;k++){                ret.data[i][j]=(ret.data[i][j]+(x.data[i][k]*y.data[k][j])%MOD)%MOD;            }        }    }    return ret;}Mat Mpow(Mat x,ll t){    Mat ret;    ret.data[1][1]=ret.data[2][2]=1;    while(t){        if(t&1) ret=mut(x,ret);        x=mut(x,x);        t>>=1;      }    return ret;}int main(){    cin>>n;    Mat o;    o.data[1][1]=o.data[1][2]=o.data[2][1]=1;    o=Mpow(o,n);    cout<