M斐波那契数列F[n]是一种整数数列，它的定义如下：
F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n，你能求出F[n]的值吗？
通过简单地列出若干项 F 即可发现，某一项的值是由若干 a 和 b 相乘得到的，而他们的指数是连续的两项斐波那契数。
因此可以通过斐波那契数列的矩阵快速幂求法得到，注意需要指数的降幂公式。
1 #include<stdio.h>
2 #include<string.h>
3 typedef long long ll;
4 const int mod=1000000007;
5 const int mmod=1000000006;
6 struct mat{
7 int r,c;
8 ll m[5][5];
9 void clear(){
10 for(int i=1;i<=r;i++)memset(m[i],0,sizeof(m[i]));
11 }
12 };
13
14 int read(){
15 int x=0;
16 char c=getchar();
17 while(c>'9'||c<'0')c=getchar();
18 while(c>='0'&&c<='9'){
19 x=x*10+c-'0';
20 c=getchar();
21 }
22 return x;
23 }
24
25 mat MatMul(mat &m1,mat &m2){
26 mat tmp;
27 tmp.r=m1.r;
28 tmp.c=m2.c;
29 int i,j,k;
30 for(i=1;i<=tmp.r;i++){
31 for(j=1;j<=tmp.c;j++){
32 ll t=0;
33 for(k=1;k<=m1.c;k++){
34 t=(t+(m1.m[i][k]*m2.m[k][j])%mmod)%mmod;
35 }
36 tmp.m[i][j]=t;
37 }
38 }
39 return tmp;
40 }
41
42 mat MatQP(mat &a,int n){
43 mat ans,tmp=a;
44 ans.r=ans.c=a.r;
45 memset(ans.m,0,sizeof(ans.m));
46 for(int i=1;i<=ans.r;i++){
47 ans.m[i][i]=1;
48 }
49 while(n){
50 if(n&1)ans=MatMul(ans,tmp);
51 n>>=1;
52 tmp=MatMul(tmp,tmp);
53 }
54 return ans;
55 }
56
57 ll QP(ll a,ll n){
58 ll tmp=a,ans=1;
59 while(n){
60 if(n&1)ans=ans*tmp%mod;
61 tmp=tmp*tmp%mod;
62 n>>=1;
63 }
64 return ans%mod;
65 }
66
67 int main(){
68 int x,y,n;
69 mat t,tmp;
70 t.r=2;t.c=2;
71 t.clear();
72 t.m[1][2]=t.m[2][1]=t.m[2][2]=1;
73 mat a;
74 a.r=2;
75 a.c=1;
76 a.m[1][1]=0;
77 a.m[2][1]=1;
78 ll ans;
79 while(scanf("%d%d%d",&x,&y,&n)!=EOF){
80 if(n==0)printf("%d
",x);
81 else{
82 tmp=MatQP(t,n-1);
83 tmp=MatMul(tmp,a);
84 ans=QP(x,tmp.m[1][1])*QP(y,tmp.m[2][1])%mod;
85 printf("%lld
",ans);
86 }
87 }
88 return 0;
89 }