题意：

定义，求

解法一（递推法）

我们设，显然有
我们发现，那么我们可设，显然有
同理我们可得，设，显然有
于是我们就可以做到用线性复杂度求解本题了。
代码： 
class Solution {
public:
    const int mod=1e9+7;
    int f[1000000001];
    int T[1000000001];
    int G[1000000001];
    int F[1000000001];
    int getSum(int n) {
        /*边界值*/
        f[0]=0;
        f[1]=1;
        T[1]=1;
        G[1]=1;
        F[1]=1;
        for(int i=2;i<=n;i++){
            f[i]=(f[i-1]+f[i-2])%mod;//f(2)=f(1)+f(0)=1
            T[i]=(T[i-1]+f[i])%mod;//\sum_{i=1}^nf(i)
            G[i]=(G[i-1]+T[i])%mod;//\sum_{i=1}^nT(i)
            F[i]=(F[i-1]+G[i])%mod;//\sum_{i=1}^nG(i)
        }
        return F[n];
    }
};
时间复杂度：，我们需要递推第项的值，单次递推是的，故总的时间复杂度为
空间复杂度：，数组都是大小的，故总的空间复杂度为

解法二（矩阵快速幂）

由
可推出
即：
由
可推出
即：
由
可推出
即：
于是我们可以构造矩阵乘法式子：
于是有
我们就可以利用矩阵快速幂算法求解了。
具体的，为了方便起见，我们可以直接三重循环暴力求解（由于数值较小，对应的时间复杂度可视为常数）。
代码： 
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    static const int mod=1e9+7;
    struct mat{
        int A[5][5];
        inline mat(){
            memset(A,0,sizeof A);
        }
        inline int* operator [] (int p){
            return A[p];
        }
        inline mat operator * (const mat& other)const{
            mat ret;
            for(int i=0;i<5;i++){
                for(int j=0;j<5;j++){
                    for(int k=0;k<5;k++){
                        //矩阵乘法
                        ret.A[i][j]=(ret.A[i][j]+1ll*A[i][k]*other.A[k][j]%mod)%mod;
                    }
                }
            }
            return ret;
        }
    };
    mat ksm(mat a,int b){
        //矩阵快速幂
        mat ret;
        for(int i=0;i<5;i++)ret.A[i][i]=1;//单位矩阵
        while(b){
            if(b&1){
                ret=ret*a;
            }
            a=a*a;
            b>>=1;
        }
        return ret;
    }
    int f[6];
    int F[6];
    int getSum(int n) {
        f[0]=0,f[1]=1;
        for(int i=2;i<=5;i++){
            f[i]=(f[i-1]+f[i-2])%mod;
        }
        memset(F,0,sizeof F);
        for(int p=1;p<=5;p++){
            for(int i=1;i<=p;i++){
                for(int j=1;j<=i;j++){
                    for(int k=1;k<=j;k++){
                        F[p]=(F[p]+f[k])%mod;//前5个直接暴力求解
                    }
                }
            }
        }
        if(n<=5)return F[n];
        mat t;
        t[0][0]=4,t[0][1]=(-5+mod)%mod,t[0][2]=1,t[0][3]=2,t[0][4]=(-1+mod)%mod;
        t[1][0]=1,t[2][1]=1,t[3][2]=1,t[4][3]=1;//初始化矩阵
        t=ksm(t,n-5);
        int ans=0;
        for(int i=0;i<5;i++){
            ans=(ans+1ll*t[0][i]*F[5-i]%mod)%mod;//模拟矩阵乘法求解答案
        }
        return ans;
    }
};
时间复杂度：，其中是矩阵一次乘法运算的复杂度，本题中，一共需要进行次乘法运算，故总的时间复杂度为
空间复杂度：，为矩阵大小，程序中我们只需要保存级别个矩阵即可，故空间复杂度为