题目链接：

题意：F[0]=a,F[1]=b,F[n]=F[n-1]*F[n-2]。

思路：手算一下可以发现，最后F[n]=a^x*b^y，其中x和y是连续的两项Fib。因此只要求出这两个系数x和y即可。注意这里A^x=A^(x%Phi(C)+Phi(C)) (mod C)。因此在求矩阵快速幂时模的数不是mod=1000000007，而是mod-1。

 

struct matrix{    i64 a[2][2];    void init(int x)    {        clr(a,0);        if(x) a[0][0]=a[1][1]=1;    }    matrix operator*(matrix p)    {        matrix ans;        ans.init(0);        int i,j,k;        FOR0(k,2) FOR0(i,2) FOR0(j,2)        {            ans.a[i][j]+=a[i][k]*p.a[k][j]%(mod-1);            ans.a[i][j]%=(mod-1);        }        return ans;    }    matrix pow(int n)    {        matrix ans,p=*this;        ans.init(1);        while(n)        {            if(n&1) ans=ans*p;            p=p*p;            n>>=1;        }        return ans;    }};matrix p;int a,b,n;i64 Pow(i64 a,i64 b){    i64 ans=1;    while(b)    {        if(b&1) ans=ans*a%mod;        a=a*a%mod;        b>>=1;    }    return ans;}int main(){    p.a[0][0]=p.a[1][0]=p.a[0][1]=1;    p.a[1][1]=0;    Rush(a)    {        RD(b,n);        if(n==0) PR(a);        else if(n==1) PR(b);        else        {            matrix temp=p.pow(n-2);            int x=(temp.a[0][1]+temp.a[1][1])%(mod-1);            int y=(temp.a[0][0]+temp.a[1][0])%(mod-1);            PR(Pow(a,x)*Pow(b,y)%mod);        }    }}