1131 - 求递推序列的第N项
描述

有一个序列是这样定义的: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。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)


输出

输出f(n)的值。


样例

输入

3 -1 5

输出

6
提示

题目中 N 的范围为 1e9 ,直接计算是不可行的。
根据同余,我们知道这个递推式 %7 的结果一定会出现循环。
这是因为:序列中的每一项的值是由前两项决定的,如果前两项 %7 出现了重复,则后面会一直重复下去。 而前两项的值 %7 的结果,不超过 49 种,
因此我们用一个数组来记录上一次出现这个 ai−1%7 , ai−2%7 是哪一项,这样我们就可以计算出循环的长度。 最终计算的 f(n) 也会通过循环,转为 49 项之内的某个值。

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1