问题描述】

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

【输入格式】

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

【输出格式】

输出仅一行，一个整数，即$f(n)$的值。

【输入样列】

1 1 3

【输出样列】

2
说明：若输入样例为1 2 10，则输出为5。

【数据规模】

$20$%的数据，$n$≤$1,000$

$40$%的数据，$n$≤$100,000$

$100$%的数据，$n$≤$100,000,000$