F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )

现在给出a, b, n，你能求出F[n]的值吗？

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

using namespace std;

#define INF 0x3f3f3f3f

#define MM(x) memset(x,0,sizeof(x))

#define MMINF(x) memset(x,INF,sizeof(x))

typedef long long LL;

const double PI=acos(-1.0);

const LL mod=1000000007;

struct mat

{

	LL pos[2][2];

	mat(){MM(pos);}

};

mat operator*(const mat &a,const mat &b)

{

	mat c;

	for (int i=0; i<2; i++)

	{

		for (int j=0; j<2; j++)

		{

			for (int k=0; k<2; k++)

			c.pos[i][j]+=(a.pos[i][k]*b.pos[k][j])%(mod-1);

		}

	}

	return c;

}

mat operator^(mat a,LL b)

{

	mat r;

	for (int i=0; i<2; i++)

		r.pos[i][i]=1;

	while (b!=0)

	{

		if(b&1)

			r=r*a;

		a=a*a;

		b>>=1;

	}

	return r;

}

LL qpow(LL a,LL b)

{

	LL r=1;

	a%=mod;

	while (b)

	{

		if(b&1)

			r=(r*a)%mod;

		a=(a*a)%mod;

		b>>=1;

	}

	return r;

}

int main(void)

{

	LL pa,pb;

	LL a,b,c,n;

	while (~scanf("%I64d%I64d%I64d",&a,&b,&n))

	{

		if(n==0)

			printf("%I64d\n",a);

		else if(n==1)

			printf("%I64d\n",b);

		else

		{

			mat t,one;

			t.pos[0][0]=1;

			t.pos[0][1]=1;

			t.pos[1][0]=1;

			one.pos[0][0]=1;

			one.pos[1][0]=1;

			t=t^(n-2);

			one=t*one;

			pa=one.pos[1][0]%(mod-1);

			pb=one.pos[0][0]%(mod-1);

			printf("%I64d\n",(qpow(a,pa)*qpow(b,pb))%mod);

		}

	}

	return 0;

}