基准时间限制：1 秒 空间限制：131072 KB 分值: 10

难度：2级算法题

有一个序列是这样定义的：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

给出A，B和N，求f(n)的值。

Input

输入3个数：A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)

Output

输出f(n)的值。

Input示例

3 -1 5

Output示例

6

问题链接：

问题分析：本题与《》类似，输入的值的范围不同，参见参考链接。

这是一个有关序列与模除的问题，有点像斐波拉契数列，只是第i项是由一个公式计算的，并且使用了模除。

根据数论的知识可知，模7的余数值是0-6。若对于正整数k和m，若f(k-2)=f(m-2)且f(k-1)=f(m-1)，则f(k)=f(k-2)+f(k-1)=f(m-2)+f(m-1)=f(m)，即如果k和m的前两项完全相同，则f(k)=f(m)。这样的数列，若干项之后，其值会循环出现，所以不必将其所有的项都算出来，只需要算出第一个循环的各个项即可。

因此，只需要构建一个长度为n的短数列，各项的值为定义公式计算出来的7的余数，需要知道的是n为多少。如果f(n+1)=1（f(1)=1）且f(n+2)=1（f(2)=1），那么就得到了所要求的n了。

程序说明：需要取一个合适的N，保证能够出现循环。

题记：（略）

参考链接：

AC的C++程序如下：

#include 
    
     using namespace std;const int MOD = 7;const int N = 110;int t[N] = {0, 1, 1};int main(){    int a, b, n, i;    while(cin >> a >> b >> n) {        if(n == 1 || n == 2) {            ;        } else {            for(i=3; i