Problem Description

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).

 

Input

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.

 

Output

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

 

Sample Input

 

Sample Output

#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;

typedef long long LL;

#define INF 0x3f3f3f3f

struct mat

{

	int pos[2][2];

	mat(){memset(pos,0,sizeof(pos));}

};

inline 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])%7;

			}

		}

	}

	return c;

}

inline mat operator^(mat a,LL b)

{

	mat r;r.pos[0][0]=r.pos[1][1]=1;

	mat bas=a;

	while (b!=0)

	{

		if(b&1)

			r=r*bas;

		bas=bas*bas;

		b>>=1;

	}

	return r;

}

int main(void)

{

	ios::sync_with_stdio(false);

	int n,a,b;

	while (cin>>a>>b>>n&&(a||b||n))

	{

		if(n==1)

		{

			cout<<1<<endl;

			continue;

		}

		mat one,t;

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

		t.pos[0][0]=a,t.pos[0][1]=b;t.pos[1][0]=1;

		t=t^(n-2);

		one=t*one;

		cout<<one.pos[0][0]%7<<endl;

	}

	return 0;

}