my code
#include<bits/stdc++.h>
using namespace std;
#define endl “\n”
#define sd(val) scanf("%d",&val)
#define ss(val) scanf("%s",&val)
#define sl(val) scanf("%lld",&val)
#define all(v) v.begin(),v.end()
#define PB push_back
#define MP make_pair
#define FF first
#define SS second
#define ll long long int
#define MOD 1000000007
#define clr(val) memset(val,0,sizeof(val))
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
vectorb,c,a;ll k;
vector<vector> multiply(vector<vector>A,vector<vector>B)
{
vector<vector>C(k+1,vector(k+1));
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
for(int m=1;m<=k;m++)
{
C[i][j]=(C[i][j]+(A[i][m]*B[m][j])%MOD)%MOD;
}
}
}
return C ;
}
vector<vector> pow(vector<vector>A,ll p)
{
if(p==1)
{
return A;
}
else
{
if(p&1)
return multiply(A,pow(A,p-1));
else
{
vector<vector>X=pow(A,p/2);
return multiply(X,X);
}
}
}
ll compute(ll n)
{
if(n==0)
{
return 0;
}
else if(n<=k)
{
return b[n-1];
}
vectorf1(k+1);
for(int i=1;i<=k;i++)
{
f1[i]=b[i-1];
}
// Forming transformation matrix
vector<vector>t(k+1,vector(k+1));
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
if(i<k)
{
if(j==i+1)
{
t[i][j]=1;
}
else
{
t[i][j]=0;
}
}
else
{
t[i][j]=c[k-j];//since c is 0 indexed
}
}
}
t=pow(t,n-1);
//We have obtained t^n-1
ll res=0;
for(int i=1;i<=k;i++)
{
res=(res+(t[1][i]*f1[i])%MOD)%MOD;
}
return res;
}
int main()
{
ll t;
cin>>t;
while(t–)
{
cin>>k;
ll num=0;
for(ll i=0;i<k;i++)
{
cin>>num;
b.push_back(num);
}
for(ll i=0;i<k;i++)
{
cin>>num;
c.push_back(num);
}
ll n;
cin>>n;
ll ans=compute(n);
cout<<ans<<endl;
b.clear();
c.clear();
}
return 0;
}
