#include using namespace std; using ll =long long; #include using namespace atcoder; using mint=modint1000000007; using vm=vector; using vvm=vector; vvm M1={ {1,0,0,0,0,0,0}, {1,1,0,0,0,0,1}, {0,0,1,0,0,0,0}, {1,0,1,1,0,0,1}, {0,0,0,0,1,0,0}, {1,0,2,0,1,1,1}, {0,0,0,0,0,0,1} }; vvm M0={ {1,1,0,0,0,0,1}, {0,1,0,0,0,0,0}, {0,1,1,1,0,0,1}, {0,0,0,1,0,0,0}, {0,1,0,2,1,1,1}, {0,0,0,0,0,1,0}, {0,0,0,0,0,0,1} }; vvm E={ {1,0,0,0,0,0,0}, {0,1,0,0,0,0,0}, {0,0,1,0,0,0,0}, {0,0,0,1,0,0,0}, {0,0,0,0,1,0,0}, {0,0,0,0,0,1,0}, {0,0,0,0,0,0,1} }; vvm mul(vvm A,vvm B){ ll n=A.size(); vvm C(n,vm(n,0)); for(int i=0;i>T; ll N=T.size(),K; cin>>K; vector> cum(N+1,vector(2,0)),sum(N+1,vector(2,0)),dum(N+1,vector(2,0)); vvm D=E; for(int i=0;i0){ if(K%2){ AN=mul(AN,D); } K/=2; D=mul(D,D); } cout<<(AN[5][6]+AN[4][6]).val()<>T; while(T--)solve(); }