Water Problem

函数 $\mathrm{f:Z+\to Z}$

的值。

多组数据。（数据组数 $\mathrm{T\le 100}$

的值。

 输出 $\mathrm{f(n)mod(109+7)}$

。每组输出末尾有换行符。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
using namespace std;
typedef long long ll;
const long long mod = 1e9+7;
const long long N = 4;
ll f1,f2;
int n;
struct Fast_Matrax
{
 
    ll a[N][N];
    Fast_Matrax()
    {
        memset(a,0,sizeof(a));
    }
    void init()
    {
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                a[i][j]=(i==j);
    }
    Fast_Matrax operator * (const Fast_Matrax &B)const
    {
        Fast_Matrax C;
        for(int i=0;i<N;i++)
            for(int k=0;k<N;k++)
                for(int j=0;j<N;j++)
                    C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j]%mod+mod)%mod;
        return C;
    }
    Fast_Matrax operator ^ (const int &t)const
    {
        Fast_Matrax A=(*this),res;
        res.init();
        int p=t;
        while(p)
        {
            if(p&1)res=res*A;
            A=A*A;
            p>>=1;
        }
        return res;
    }
}ans,tmp,x;
int main()
{
    while(~scanf("%lld%lld%d",&f1,&f2,&n))
    {
        x.a[0][0]=f2;x.a[0][1]=f1;x.a[0][2]=1,x.a[0][3]=0;
        if(n==1)printf("%lld\n",f1);
        else if(n==2)printf("%lld\n",f2);
        else
        {
            tmp.a[0][0]=1;tmp.a[0][1]=1;tmp.a[0][2]=0;tmp.a[0][3]=0;
            tmp.a[1][0]=1;tmp.a[1][1]=0;tmp.a[1][2]=0;tmp.a[1][3]=0;
            tmp.a[2][0]=0;tmp.a[2][1]=0;tmp.a[2][2]=0;tmp.a[2][3]=-1;
            tmp.a[3][0]=1;tmp.a[3][1]=0;tmp.a[3][2]=1;tmp.a[3][3]=0;
            ans=x*(tmp^(n-2));
            printf("%lld\n",ans.a[0][0]);
        }
    }
    return 0;
}