Description
令F(i)表示斐波那契数列的第i项。
S1(i)表示F数列的前i项和。
S2(i)表示S1数列的前i项和。
S3(i)表示S2数列的前i项和。
S4(i)表示S3数列的前i项和。
S5(i)表示S4数列的前i项和。
S6(i)表示S5数列的前i项和。
S7(i)表示S6数列的前i项和。
S8(i)表示S7数列的前i项和。
求S8(N)。答案可能很大，请对1000000007取模。
斐波那契数列的定义可以查看https://baike.baidu.com/item/斐波那契数列

Input
多组数据。
输入的第一行包括一个整数表示数据组数T(1<=T<=1000)。
每组数据的第一行包括一个整数表示题目所说的N(1<=N<=1000000000000000000)。

Output
每组数据在单独的一行中输出S8(N)。


Sample Input
4
1
2
3
4
Sample Output
1
9
46
175
HINT
F数列前四项：1 1 2 3

S1数列前四项：1 2 4 7

S2数列前四项：1 3 7 14

S3数列前四项：1 4 11 25

S4数列前四项：1 5 16 41

S5数列前四项：1 6 22 63

S6数列前四项：1 7 29 92

S7数列前四项：1 8 37 129

S8数列前四项：1 9 46 175 

由题目给的hint其实已经看出来了[latex]S_n^8=S_{n-1}^{87654321}+F_n[/latex]

其他项也是如此

#include
using namespace std;
typedef long long ll;
ll p=1000000007;
struct Mat{
    ll a[10][10];
    Mat(){
        memset(a,0,sizeof(a));
    }
};
Mat mul(Mat a,Mat b)
{
    Mat res=Mat();
    for(ll i=0;i<10;i++)
    {
        for(ll j=0;j<10;j++)
        {
            for(ll k=0;k<10;k++)
            {
                if(a.a[i][k]&&b.a[k][j])
                res.a[i][j]+=(a.a[i][k]%p)*(b.a[k][j]%p)%p; 
            }   
        }   
    }   
    return res;
} 
Mat ksm(Mat n,ll k)
{
    Mat ans=Mat();
    for(ll i=0;i<10;i++)
    ans.a[i][i]=1;
    while(k)
    {
        if(k&1) ans=mul(n,ans);
        n=mul(n,n);
        k>>=1;
    }
    return ans;
}
int main()
{
    ll t;
    ll temp1[10][10]={
        {1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,0},
        {0,0,1,1,1,1,1,1,1,0},
        {0,0,0,1,1,1,1,1,1,0},
        {0,0,0,0,1,1,1,1,1,0},
        {0,0,0,0,0,1,1,1,1,0},
        {0,0,0,0,0,0,1,1,1,0},
        {0,0,0,0,0,0,0,1,1,0},
        {0,0,0,0,0,0,0,0,1,1},
        {0,0,0,0,0,0,0,0,1,0}
        };
    ll temp2[10][10]={
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0}
        };
    scanf("%lld",&t);
    for(ll i=1;i<=t;i++)
    {
        ll n;
        scanf("%lld",&n);
        Mat a=Mat();        
        memcpy(a.a,temp1,sizeof(temp1));
        Mat inim=Mat();     
        memcpy(inim.a,temp2,sizeof(temp2));
        Mat d=Mat();
        d=mul(ksm(a,n-1),inim);
        printf("%lld\n",d.a[0][0]%p);
    }
}