Solution：
1.快速幂：数/矩阵
2.以证明1000000007是素数。
费马小定理：
若p是素数，gcd(a,p)=1,则a^(p-1)1(mod p)。
若a^b mod p 中b很大，则可以简化为a^b mod p=a^[b mod (p-1)] mod p
证明如下：
b=t*(p-1)+r，其中r为b除以(p-1)的余数，即为b mod (p-1)。
a^b=(a^(p-1))^t * a^r 1^t * a^r
a^r (mod p)
费马小定理的推广：如果p为质数，xp-x（x是任意正整数）必能被p整除
注意是对b，对结果分别是取模(p-1)，取模p；不要同时取模p或同时取模(p-1)！
#include <stdio.h>
#include <stdlib.h> #define yu_ 1000000006
#define yu 1000000007 int main()
{
//f[n]=a^x(n-1)*b^x(n)
//a^f(n-1) = a^(f(n-1)%1000000006) (mod 1000000007)
//1000000007 is a prime
long n,nn,w,i,c[];
__int64 x[],y[],u[],v[],p,q,s,t,pp,qq,ss,tt,a,b,result;
x[]=;
y[]=;
u[]=;
v[]=;
for (i=;i<;i++)
{
x[i]=(x[i-]*x[i-]+y[i-]*u[i-])%yu_;
y[i]=(y[i-]*(x[i-]+v[i-]))%yu_;
u[i]=(u[i-]*(x[i-]+v[i-]))%yu_;
v[i]=(y[i-]*u[i-]+v[i-]*v[i-])%yu_;
}
while (scanf("%ld%ld%ld",&c[],&c[],&n)!=EOF)
{
if (n==)
{
printf("%ld\n",c[]);
continue;
}
else if (n==)
{
printf("%ld\n",c[]);
continue;
}
result=;
for (i=;i<;i++)
{
p=;
q=;
s=;
t=;
//a:n-2 b:n-1
nn=n+i-;
w=;
while (nn)
{
if ((nn & )==)
{
pp=p;
qq=q;
ss=s;
tt=t;
p=(pp*x[w]+qq*u[w])%yu_;
q=(pp*y[w]+qq*v[w])%yu_;
s=(ss*x[w]+tt*u[w])%yu_;
t=(ss*y[w]+tt*v[w])%yu_;
}
w++;
nn>>=;
}
//f(n)/f(n+1)
p=(p+q)%yu_;
a=;
b=c[i];
while (p)
{
if ((p & )==)
a=(a*b)%yu;
p>>=;
b=(b*b)%yu;
}
result=(result*a)%yu;
}
printf("%I64d\n",result);
}
return ;
}