M斐波那契数列F[n]是一种整数数列，它的定义如下：

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

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

输入包含多组测试数据；
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）

对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。

0 1 0

6 10 2

0

60

2013金山西山居创意游戏程序挑战赛——初赛（2）

   题目中  f[n] =a ^? * b^? ，a，b的指数，刚好可以使用斐波那契数列求解，

   矩阵快速幂求斐波那契数列

 

  费马小定理：

    若p是质数，且gcd（a，p）=1，则  a ^ (p-1) = 1 (mod p)

 

#include <iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int mod=;

long long a,b;

int n;

long long pow(long long a,long long b)

{

    long long res=;

    while(b)

    {

        if (b&) res=(res*a)%mod;

        a=(a*a)%mod;

        b>>=;

    }

    return res;

}

long long mul(int n)

{

    long long t[][]={,,,};//相当于pow中的a

    long long ans[][]={,,,};//存最后的结果

    long long tmp[][]; // 临时的

    while(n)

    {

        if (n&)

        {

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

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

                  tmp[i][j]=ans[i][j],ans[i][j]=;

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

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

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

                        ans[i][j]=(ans[i][j]+tmp[i][k]*t[k][j])%(mod-);

        }

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

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

           { tmp[i][j]=t[i][j]; t[i][j]=;}

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

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

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

                  t[i][j]=(t[i][j]+tmp[i][k]*tmp[k][j])%(mod-);

        n>>=;

    }

  return (pow(a,ans[][])*pow(b,ans[][]))%mod;

}

int main()

{

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

    {

       if (n==) printf("%lld\n",a%mod);

        else if (n==) printf("%lld\n",b%mod);

         else printf("%lld\n",mul(n));

    }

    return ;

}