Jzzhu has invented a kind of sequences, they meet the following property:
You are given x and y, please calculate fn modulo 1000000007 (109?+?7).
Input
The first line contains two integers x and y (|x|,?|y|?≤?109). The second line contains a single integer n (1?≤?n?≤?2·109).
Output
Output a single integer representing fn modulo 1000000007 (109?+?7).
Examples
Input
2 3 3
Output
1
Input
0 -1 2
Output
1000000006
【CodeForces - 450B Jzzhu and Sequences 规律】Note
In the first sample, f2?=?f1?+?f3, 3?=?2?+?f3, f3?=?1.
In the second sample, f2?=??-?1; ?-?1 modulo (109?+?7) equals (109?+?6).
题意：给定序列f[1] = x, f[2] = y,f[i] = f[i + 1] + f[i - 1]，求 f[n]
题解：f[i] = f[i - 1] - f[i - 2]先别着急矩阵快速幂啊 写几个看看
abb-a-a-b-b+aab这不就6个一循环了嘛，注意取模就行了
#include
using namespace std;
const int mod=1e9+7;
int a[15];
int n;
int main() {
while(~scanf("%d%d",&a[1],&a[2]))
{
a[1]=(a[1]%mod+mod)%mod;
a[2]=(a[2]%mod+mod)%mod;
for(int i=3;
i<=6;
i++)
{
a[i]=((a[i-1]-a[i-2])%mod+mod)%mod;
}
scanf("%d",&n);
n%=6;
if(n==0) n=6;
cout< 推荐阅读
- AIoT(人工智能+物联网)|程序员的数学【线性代数基础】
- topcoder|Topcoder SRM 661 Div1 Easy: MissingLCM
- HDU 5184 Brackets (卡特兰数)
- 高斯消元
- 水题纪念|【51nod - 1098】 最小方差（基础数学，公式化简，前缀和，积的前缀和）
- 扩展欧几里德算法（gcd扩展使用）
- 数学|CF 514D.Nature Reserve 几何,二分,交集
- codeforces|Codeforces Round #665 (Div. 2) C. Mere Array(数学)
- codeforces|Codeforces Round #665 (Div. 2) A. Distance and Axis(思维，数学)
- 数论|Codeforces Global Round 10 B. Omkar and Infinity Clock(数学)