M斐波那契数列F[n]是一种整数数列，它的定义如下： F[0] = a F[1] = b F[n] = F[n-1] * F[n-2] ( n > 1 ) 现在给出a, b, n，你能求出F[n]的值吗？
Input
输入包含多组测试数据； 每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）
Output
对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。
Sample Input
0 1 0 6 10 2Sample Output
0 60F(n)不是线性递推式，先推一下规律：
F(0)=a
F(1)=b
F(2)=a*b
F(3)=(a^1)*(b^2)
F(4)=(a^2)*(b^3)
F(5)=(a^3)*(b^5)
……
发现F(n)=(a^f(n-2))*(b^f(n-1))
其中f(n)为斐波那契序列，f(0)=1,f(1)=1,f(2)=2……
两个幂之积然后取模一个素数，由费马小定理：
(a^b)%p=a^(b%(p-1))
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2; const int MOD=1e9+7; struct mat { ll a[N][N]; }; mat mat_mul(mat x,mat y) { mat res; memset(res.a,0,sizeof(res.a)); for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++) res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%(MOD-1);///费马小定理 return res; } mat mat_pow(ll n) { mat c,res; c.a[0][0]=c.a[0][1]=c.a[1][0]=1; c.a[1][1]=0; memset(res.a,0,sizeof(res.a)); res.a[0][0]=res.a[1][1]=1; while(n) { if(n&1) res=mat_mul(res,c); c=mat_mul(c,c); n=n>>1; } return res; } ll quick(ll a,ll b) { ll ans=1; a%=MOD; while(b) { if(b&1) ans=((ans%MOD)*(a%MOD))%MOD; a=((a%MOD)*(a%MOD))%MOD; b>>=1; } return ans; } int main() { ll n,x,y; while(~scanf("%lld%lld%lld",&x,&y,&n)) { if(x==0||y==0) { cout<<0<<'\n'; continue; } if(n==0) { cout<<x%MOD<<'\n'; continue; } if(n==1) { cout<<y%MOD<<'\n'; continue; } mat res=mat_pow(n-2); ll tmp1=(res.a[0][0]%(MOD-1)+res.a[0][1]%(MOD-1))%(MOD-1);///两个指数取模（MOD-1） ll tmp2=(res.a[1][0]%(MOD-1)+res.a[1][1]%(MOD-1))%(MOD-1); // cout<<tmp1<<' '<<tmp2<<'\n'; ll ans1=quick(x,tmp2%(MOD-1)); ll ans2=quick(y,tmp1%(MOD-1)); ll ans=((ans1%MOD)*(ans2%MOD))%MOD;///乘法取模（正常） cout<<ans<<'\n'; } return 0; } //f(n) 1 1 f(1) //f(n-1) 1 0 f(0)
