14015: 【原4015】怎么还是那个数列？！

题目

题目描述

author: Naïve Yan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4015 ## Description 你费劲口舌和很多小朋友不断交换位置,好不容易来到小X大牛家，并且询问了你最困惑的那个“斐波那契数列”问题和“树的存储结构和性质”问题,准备拜谢后离开，没想到小X大牛对你印象不错，认为你很有灵气，于是乎，他就顺便出了下面这个题目给你回家思考。

一个数列定义如下：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

输入一行包含3个整数A，B和n，1 ≤ A, B ≤ 1000,1 ≤ n ≤ 100000000)。

Output Format

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

Sample Input 1

1 1 3

Sample Output 1

2

Sample Input 2

1 2 10

Sample Output 2

5

Limits

20%的数据，n ≤ 1000；

40%的数据，n ≤ 100000；

100%的数据，n ≤ 100000000。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！