I dont know what is wrong with the code , Please Check
#include <bits/stdc++.h>
#include
#include
#include
#include
#include
#include
#define endl “\n”
#define ll long long int
#define vi vector
#define vll vector
#define vvi vector
#define pii pair<int, int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all© c.begin(), c.end()
#define mp(x, y) make_pair(x, y)
#define mem(a, val) memset(a, val, sizeof(a))
#define eb emplace_back
#define f first
#define s second
#define p_b push_back
using namespace std;
ll k;
vector a, b, c;
vector<vector> multiply(vector<vector> A, vector<vector> B)
{
// MATRIX C to store the final result;
vector<vector> C(k + 1, vector(k + 1));
//logic to multiply matrices
for (int i = 1; i <= k; i++)
{
for (int j = 1; j < = k; j++)
{
for (int x = 1; x <= k; x++)
{
C[i][j] = (C[i][j] + (A[i][x] * B[x][j]) % mod) % mod;
}
}
}
return C;
}
vector<vector> pow(vector < vector A, ll p)
{
//base case
if (p == 1)
return A;
// if (p == 0)
// return 1;
// if power is odd
if (p & 1)
{
return multiply(A, pow(A, p - 1));
}
vector<vector<ll>> X = pow(A, p / 2);
return multiply(X, X);
}
ll compute(ll n)
{
if (n == 0) //base case
return 0;
if (n <= k) //we have coeffcients till here
return b[n - 1];
//NOW TO COMPUTE USING MATRIX EXPONENTIATION
vector<ll> F1(k + 1);
//indexing from 1;
for (int i = 1; i <= k; i++)
{
F1[i] = b[i - 1];
}
//Transformation Matrix
vector<vector<ll>> T(k + 1, vector<ll>(k + 1)); //Matrix is from 1,1 to k,k;
for (int i = 1; i <= k; i++)
{
for (int j = 1; i <= k; i++)
{
if (i < k)
{
if (j == i + 1)
{
T[i][j] = 1;
}
else
{
T[i][j] = 0;
}
}
else
{
T[i][j] = c[k - j];
}
}
}
T = pow(T, n - 1);
// MAtrix multiply with A
ll res = 0;
for (int i = 1; i <= k; i++)
{
res = (res + (T[1][i] * F1[i][1]) % mod) % mod;
}
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
ll t, n, num;
cin >> t;
while (t--)
{
cin >> k;
for (int i = 0; i < k; i++)
{
cin >> num;
b.p_b(num);
}
for (int i = 0; i < k; i++)
{
cin >> num;
c.p_b(num);
}
cin >> n;
cout << compute(n) << endl;
b.clear();
c.clear();
}
return 0;
}
