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

找规律，矩阵快速幂，快速幂，费马小定理

#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1000000007;
struct mat{
	long long m[3][3];
};
mat operator*(mat a,mat b){
	mat ans;
	memset(ans.m,0,sizeof(ans.m));
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			for(int k=1;k<=2;k++)
			ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%(mod-1);
		}
	}
	return ans;
}
mat ksm(mat a,long long b){
	mat s;
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			if(i==j) s.m[i][j]=1;
			else s.m[i][j]=0;
		}
	}
	while(b){
		if(b&1) s=s*a;
		b>>=1;
		a=a*a;
	}
	return s;
}
long long f(long long a,long long b){
	long long s=1;
	while(b){
		if(b&1) {
		s=s%mod;
		a=a%mod; 
		s=s*a;
		}	
		a=a%mod;
		a=a*a;
		b>>=1;
	}
	return s%mod;
}
int main(){
	int a,b,n;
	mat m;
	m.m[1][1]=m.m[1][2]=m.m[2][1]=1;
	m.m[2][2]=0;	
	while(~scanf("%d%d%d",&a,&b,&n)){
		if(n==0) printf("%d\n",a%mod);
		else if(n==1) printf("%d\n",b%mod);
		else{
		mat fb=ksm(m,n);
		long long p=f(a,fb.m[2][2]);
		long long q=f(b,fb.m[2][1]);
		printf("%lld\n",(p*q)%mod);
		}		
	}
	return 0;
}