A number sequence is defined as follows:
 f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. 
Given A, B, and n, you are to calculate the value of f(n).

The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

For each test case, print the value of f(n) on a single line.

1 1 3

1 2 10

0 0 0

2

5

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <algorithm>

typedef long long  ll;

#define inf 0x3f3f3f3f

#define mod 7

#include <math.h>

#include <queue>

using namespace std;

struct ma

{

    ll a[][];

} init,res;

int A,B,n;

ma mult(ma x,ma y)

{

    ma tmp;

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

    {

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

        {

            tmp.a[i][j]=;

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

            {

                tmp.a[i][j]=(tmp.a[i][j]+x.a[i][k]*y.a[k][j])%mod;

            }

        }

    }

    return tmp;

}

ma Pow(ma x,int K)

{

    ma tmp;

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

    {

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

        {

            tmp.a[i][j]=(i==j);

        }

    }

    while(K)

    {

        if(K&) tmp=mult(x,tmp);

        K>>=;

        x=mult(x,x);

    }

    return tmp;

}

int main()

{

    while(scanf("%d%d%d",&A,&B,&n)!=EOF)

    {

        if(A==&&B==&&n==) break;

        if(n==||n==)

        {

            printf("1\n");

            continue;

        }

        init.a[][]=,init.a[][]=;

        init.a[][]=B,init.a[][]=A;

        res=Pow(init,(n-));

        ll sum=(res.a[][]+res.a[][])%mod;

        printf("%lld\n",sum);

    }

    return ;

}