一个数列定义如下：$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 \leq A, B \leq 1000, 1 \leq n \leq 100,000,000)$。

输出格式

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

样例

样例输入

1 1 3  

样例输出

2

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

数据范围与提示

• $20$%的数据，$n \leq 1,000$
• $40$%的数据，$n \leq 100,000$
• $100$%的数据，$n \leq 100,000,000$
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$128000\mathrm{KB}$