Description

一个数列定义如下：f(1) = 1，f(2) = 1，f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7。给定A,B和n的值，要求计算f(n)的值。

Input Format

输入文件(sequence.in)仅一行包含3个整数A，B和n，其中(1≤ A, B ≤1000, 1 ≤n≤100,000,000)。

Output Format

输出文件(sequence.out)仅一行，一个整数，即f(n)的值。

Sample

【输入样例1】

1 1 3

【输出样例1】

2

【输入样例2】

1 2 10

【输出样例2】

5

Hint

20%的数据，n≤1,000 40%的数据，n≤100,000 100%的数据，n≤100,000,000