hdu 4549 M斐波那契数列 数论 矩阵

#include<iostream>
using namespace std;
typedef long long LL;

struct mat{
	LL m[2][2];
};

mat mul(mat a,mat b){
	mat ans;
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			ans.m[i][j]=0;
			for(int k=0;k<2;k++){
				ans.m[i][j]+=a.m[i][k]*b.m[k][j];
				ans.m[i][j]%=1000000006;
			}
			
		}
	}
	return ans;
}

mat qbm(mat a,LL b){
	mat ans={
	1,0,
	0,1
	};
	mat res=a;
	while(b){
		if(b&1) ans=mul(ans,res);
		res=mul(res,res);
		b>>=1;
	}
	return ans;
}

LL qbn(LL a,LL n){
	LL ans=1;
	LL res=a;
	while(n){
		if(n&1){
			ans*=res;
			ans%=1000000007;
		}
		res*=res;
		res%=1000000007;
		n>>=1;
	}
	return ans;
}

int main(){
	LL a,b,n;	
	while(~scanf("%lld%lld%lld",&a,&b,&n)){
	mat f={
	0,1,
	1,1
	};
//	cout<<a<<"  "<<b<<" "<<n;
	mat t=qbm(f,n);
//	printf("t[0][0] %lld   t[0][1] %lld   t[1][0] %lld    t[1][1] %lld\n",t.m[0][0],t.m[0][1],t.m[1][0],t.m[1][1]);
	LL ans=qbn(a,t.m[0][0])*qbn(b,t.m[0][1])%1000000007;
	
	cout<<ans<<endl;
}
}