HDU-4549 Mフィボナッチ数列

Mフィボナッチ数列HDU-4549
Mフィボナッチ数列F[n]は整数数列で、F[0]=a F[1]=b F[n]=F[n]=F[n-1]*F[n-2](n>1)現在a,b,nが与えられていますが、F[n]の値を求めることができますか?
複数のテストデータを含む入力;各グループのデータは1行を占め、3つの整数a,b,n(0<=a,b,n<=10^9)を含む.
テストデータのセットごとに整数F[n]を出力してください.F[n]が大きい可能性があるので、F[n]の1000000007型取り後の値を出力するだけで、データのセットごとに1行出力できます.
0 1 0 6 10 2
0 60
構想:マトリクス高速べき乗+指数循環節;
f(n)=a^x*b^yを発見しやすい.そしてx,yはフィポラチ数列を満たし,指数ループ節に対して
a^b%c == a^(b %phi(c)+phi(c))%c;
x,yの値を簡略化し、一般的にはマトリクスの高速べき乗でフィボラッチ数を求めるときに型を取り、
c->MODが素数である場合、phi(c)=MOD-1となる.
これは、マトリクスの高速べき乗の中でモジュールMOD-1を必要とする理由を説明します.

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define maxn 10010
#define INF 0x3f3f3f3f
#define eps 1e-8
#define MOD 1000000007
#define MOD1 1000000006
#define ll long long
using namespace std;


ll Pow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)  ans=ans*a%MOD1;
        b>>=1;
        a=a*a%MOD1;
    }
    return ans%MOD1;
}
struct Matrix{
    ll mat[2][2];
};
Matrix mul(Matrix a,Matrix b){
    Matrix ret;
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j){
            ret.mat[i][j]=0;
            for(int k=0;k<2;++k)
                ret.mat[i][j]=(ret.mat[i][j]+a.mat[i][k]*b.mat[k][j]%MOD1+MOD1)%MOD1;
        }
    return ret;
}
Matrix pow(Matrix a,ll n){
    Matrix ret;
    memset(ret.mat,0,sizeof(ret.mat));
    for(int i=0;i<2;++i)ret.mat[i][i]=1;
    Matrix tmp=a;
    while(n){
        if(n&1)ret=mul(ret,tmp);
        tmp=mul(tmp,tmp);
        n>>=1;
    }
    return ret;
}


int main()
{
    ll aa,bb,n;
    while(cin>>aa>>bb>>n)
    {
        if(n==0)   { cout<