Problem Description
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 2
Sample Output
0
60
费马小定理:(a^b)%mod =a^( b%(mod-1) )%mod
这题用矩阵快速幂求指数，求矩阵的幂，相当于求公式里的b
A^B %MOD 这题的MOD是素数，而且A，MOD是互质的。（A的最大范围是1e9）
所以直接A^(B%(MOD-1)) %MOD
# include <iostream>
# include <cstdio>
# include <algorithm>
# include <map>
# include <cmath>
# define LL long long
using namespace std ; const int MOD = ; struct Matrix
{
LL mat[][];
}; Matrix mul(Matrix a,Matrix b) //矩阵乘法
{
Matrix c;
for(int i=;i<;i++)
for(int j=;j<;j++)
{
c.mat[i][j]=;
for(int k=;k<;k++)
{
c.mat[i][j]=(c.mat[i][j] + a.mat[i][k]*b.mat[k][j])%(MOD-); //费马小定理
}
}
return c;
}
Matrix pow_M(Matrix a,int k) //矩阵快速幂
{
Matrix ans;
memset(ans.mat,,sizeof(ans.mat));
for (int i=;i<;i++)
ans.mat[i][i]=;
Matrix temp=a;
while(k)
{
if(k&)ans=mul(ans,temp);
temp=mul(temp,temp);
k>>=;
}
return ans;
} LL pow_m(LL p, LL k)
{ LL ans = ;
while(k) {
if (k & ) ans = ans * p % MOD;
p = (LL)p*p % MOD;
k >>= ;
}
return ans;
} int main ()
{
// freopen("in.txt","r",stdin) ;
int a,b,n;
Matrix t ;
t.mat[][] = ;
t.mat[][] = t.mat[][] = t.mat[][] = ;
while(scanf("%d%d%d",&a,&b,&n)!=EOF)
{
Matrix p=pow_M(t,n);
int ans=(pow_m(a,p.mat[][])*pow_m(b,p.mat[][]))%MOD;
printf("%d\n",ans);
} return ;
}