PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Kartikeya Srivastava
Tester: Taranpreet Singh
Editorialist: Kunal Tawatia
DIFFICULTY:
Medium
PREREQUISITES:
Combinatorics, Number-theoretic transform (NTT)
PROBLEM:
You are given an array A of N integers, and an integer X. For each K in the range [1,N], determine the number of ways to partition the array into exactly K non-empty subarrays such that the maxima of each of the subarrays are at least X.
The number of ways can be large, so output it modulo 998244353.
QUICK EXPLANATION:
To partition an array into K non-empty subarrays, we have to choose one starting point, L \in [1, N], corresponding to each subarray. Therefore we require k starting points, L_1, L_2, L_3, ..., L_k.
- We can reduce the original array into a binary array by keeping all the elements greater than or equal to X as 1 and remaining as 0 s.
- If the positions of 1 in A are \{p_1, p_2, p_3, ..., p_m\}, then there are (p_{i+1} - p_i) ways to select one starting point and 1 way to select no starting point in the subarray [p_i + 1, p_{i+1}] \forall i \in [1, m].
- We can model a subarray into the polynomial (p_{i+1} - p_i) \cdot x^1 + 1 \cdot x^0, where the powers of each term denote the number of starting points taken and the coefficients represent the number of ways to select that many starting points.
- We can then find the total number of ways to select starting points among all such subarrays through the polynomial \prod_{i = 1}^{m-1} ((p_{i+1} - p_i) \cdot x^1 + 1 \cdot x^0). The resulting polynomial will be of the form C_0 \cdot x^0 + C_1 \cdot x^1 + ... + C_{m-1} \cdot x^{m-1} + 0 \cdot x^{m} + ... + 0 \cdot x^{n-1}.
- The total number of ways for K-partition will be the coefficient of x^{k-1} in the resulting polynomial. Note that the initial starting point L_1 is fixed to be the index 1 of A.
We can compute the resulting polynomial by multiplication of individual polynomials, with the help of NTT. The time complexity for this approach will then remain O(N \log{N}).
EXPLANATION:
Easier Version
Let’s first solve an easier version of this problem, where we only have to find the number of ways in which we can partition the array A into subarrays such that the maximum of every partitioned subarray is at least X. Informally, this easier problem asks us to sum the answer over all Ks belonging to the original problem.
In order to solve this, we notice that to create a new partition of a non-empty subarray we only have to choose one starting point, L. We then look at this problem as finding these starting points, L_1, L_2, L_3, ..., L_k, over all the [1, N] elements of the array. Finding k starting points will give us K subarrays. Also, note that the initial starting point, L_1, will correspond to the starting position, i.e., index 1.
Without loss of generality, we can reduce the original array into a binary array by keeping all the elements greater than or equal to X as 1 and remaining as 0 s.
Now, let the positions of 1 in A be \{p_1, p_2, p_3, ..., p_m\}. The subarray [p_i + 1, p_{i+1}] \forall i \in [1, m] will look like: 00..01. This subarray of length (p_{i+1} - p_i) will have (p_{i+1} - p_i - 1) number of 0 s followed by a single 1. Our task requires us to calculate the number of ways to select starting points among all such subarrays.
A subarray can only have at max one starting point. Since if there were more, then at least one partition will be of all 0 s, and that partition will remain invalid since all the elements in the original array were less than X.
If the subarray has zero starting points, then this whole subarray will belong to the partition which was started before it, at some point L_j in some previous subarray. Elsewhen we choose one starting point at any index j, call it L_j, where j \in [p_i + 1, p_{i+1}], then this subarray will be divided into two parts, where the left part will belong to the previous partition starting at L_{j-1} and the right part will belong to the newly generated partition starting at L_j.
Thus, there are (p_{i+1} - p_i) ways to select one starting point and 1 way to select no starting point in a subarray. In total, one subarray can contribute to (p_{i+1} - p_i + 1) number of ways. Now, the total number of ways to select starting points among all such subarrays will be \prod_{i = 1}^{m-1} (p_{i+1} - p_i + 1). Note that the initial starting point L_1 is fixed to be the index 1 of A, and it belongs to the subarray [1, p_1] which is not considered in this product.
Original Version
Considering the original version of the problem, we are to report the individual number of ways for K-partition, where K \in [1, N]. We can do this using the polynomial method in combinatorics.
For a subarray [p_i + 1, p_{i+1}], we have gathered that there are (p_{i+1} - p_i) ways to select one starting point and 1 way to choose no starting point. We can model this into the polynomial (p_{i+1} - p_i) \cdot x^1 + 1 \cdot x^0, where the powers of each term denote the number of starting points taken and the coefficients represent the number of ways to select that many starting points.
We can then find the total number of ways to select starting points among all such subarrays with \prod_{i = 1}^{m-1} ((p_{i+1} - p_i) \cdot x^1 + 1 \cdot x^0). The resulting polynomial will be of the form C_0 \cdot x^0 + C_1 \cdot x^1 + ... + C_{m-1} \cdot x^{m-1} + 0 \cdot x^{m} + ... + 0 \cdot x^{n-1}. Here, the answer for K of our problem will be the coefficient of x^{k-1}. Note again that the initial starting point L_1 is fixed to be the index 1 of A, and it belongs to the subarray [1, p_1] which is not considered in this product polynomial.
In order to find the resulting polynomial, we can regard the distinct values of \{p_{i + 1} - p_i ; \forall i \in [1, m]\} as \{v_1, v_2, ..., v_t\}. Let the frequencies of \{v_1, v_2, ..., v_t\} in \{p_{i + 1} - p_i ; \forall i \in [1, m]\} be \{f_1, f_2, ..., f_t\} respectively. Since \sum_{i=1}^{t} (v_i \cdot f_i) < N, t has an upper bound of O(\sqrt{N}).
Now, the polynomial \prod_{i = 1}^{m-1} ((p_{i+1} - p_i) \cdot x^1 + 1 \cdot x^0) can be represented as \prod_{i = 1}^{t} (v_i \cdot x^1 + 1 \cdot x^0)^{f_i}. In other terms, \prod_{i = 1}^{t} (\sum_{j=0}^{f_i} \binom{f_i}{j} \cdot v_i^j \cdot x^j).
We can compute for this polynomial as a multiplication over O(\sqrt{N}) small polynomials of the form \sum_{j=0}^{f_i} \binom{f_i}{j} \cdot v_i^j \cdot x^j, that are of length f_i. The multiplication of these polynomials can be performed with Number-theoretic transform (NTT). To multiply all the individual polynomials we can sequentially pick two polynomials, multiply in O(d \cdot \log{d}), where d is the sum of degrees of the two polynomials, and keep the merged result for further multiplications. This way we can reach the final polynomial: C_0 \cdot x^0 + C_1 \cdot x^1 + ... + C_{m-1} \cdot x^{m-1} + 0 \cdot x^{m} + ... + 0 \cdot x^{n-1}, where total number of ways for K-partition will be represented by the coefficient of x^{k-1}.
We also have to take care of two corner cases:
-
All elements of A are smaller than X:
In this case, \{p_1, p_2, p_3, ..., p_m\} will be an empty set, \emptyset, i.e., m = 0.
The answer for K \in [1, N] will remain 0. -
Only one element of A is greater than or equal to X:
In this case, m = 1 and \{p_1, p_2, p_3, ..., p_m\} will contain a single element, i.e., the position of the only 1 element. For this, the only starting point will remain L_1 = 1.
Thus, the answer for K=1 will be 1, whereas for K \in [2, N] the answer remains 0.
TIME COMPLEXITY:
The calculation of the sets \{p_1, p_2, p_3, ..., p_m\}, \{v_1, v_2, ..., v_t\}, and \{f_1, f_2, ..., f_t\} shall all cost O(N) time.
Now, we want to calculate \prod_{i = 1}^{t} (v_i \cdot x^1 + 1 \cdot x^0)^{f_i}. We know that \sum_{i=1}^{t} (v_i \cdot f_i) \leq N and v_i \in [1, N) To compute the polynomial, let’s introduce j to replace v_i, and assume f_j corresponds to f_i : j = v_i. The equation \sum_{j=1}^{N} (j \cdot f_j) \leq N still holds. Then we can reframe the polynomial as \prod_{j = 1}^{N} (j \cdot x^1 + 1 \cdot x^0)^{f_j}.
The computation of individual polynomials of the form \sum_{i=0}^{f_j} \binom{f_j}{i} \cdot j^i \cdot x^i shall cost O(f_i) time using binomial theorem, i.e. O(N) time in total.
We can multiply the polynomial in reverse order:
Res = Poly(1);
for (int j = N; j > 0; j--)
Res = Res * genBinom(j, f_j);
i-th iteration works in O((f_i + f_{i+1} +…+f_N) \log{N}) time, so complete operation will take O(\log{N} \sum_{j=1}^{N} (j \cdot f_j) ) =O(N \log{N}) time. This same approach can be found here.
The time complexity for the given approach is thus O(N \log{N}).
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 1;
const int proot = 3LL;
const int mod = 998244353;
int sum,fact[N], invfact[N];
int binpow(int b, int p)
{
int r = 1;
while (p)
{
if (p & 1)
r = (r * b) % mod;
b = (b * b) % mod;
p /= 2;
}
return r;
}
void precompute()
{
fact[0] = 1;
for (int i = 1; i < N; i++)fact[i] = (fact[i - 1] * i) % mod;
for (int i = 0; i < N; i++)invfact[i] = binpow(fact[i], mod - 2);
}
int ncr(int n, int x)
{
int r = fact[n];
r = (r * invfact[x]) % mod;
r = (r * invfact[n - x]) % mod;
return r;
}
void fft(vector<int>&a, int n, bool invert, int m, int x)
{
for (int i = 0; i < n; i++)
{
int y = 0;
for (int j = 0; j < __builtin_ctzll(n); j++)
{
if ((1LL << j)&i)
y |= (1LL << (__builtin_ctzll(n) - j - 1));
}
if (y > i)swap(a[y], a[i]);
}
if (invert)x = binpow(x, mod - 2);
for (int s = 1; s < __builtin_ctzll(n) + 1; s++)
{
int y = binpow(x, n / (1LL << s));
for (int j = 0; j < (n / (1LL << s)); j++)
{
int r = 1;
for (int i = 0; i < (1LL << (s - 1)); i++)
{
int u = a[i + j * (1LL << s)];
int v = (r * a[i + j * (1LL << s) + (1LL << (s - 1))]) % m;
a[i + j * (1LL << s)] = u + v;
if (a[i + j * (1LL << s)] > m)a[i + j * (1LL << s)] -= m;
a[i + j * (1LL << s) + (1LL << (s - 1))] = u - v;
if (a[i + j * (1LL << s) + (1LL << (s - 1))] < m)a[i + j * (1LL << s) + (1LL << (s - 1))] += m;
r *= y;
r %= m;
}
}
}
if (invert)
{
int invn = binpow(n, mod - 2);
for (int i = 0; i < n; i++)a[i] = (a[i] * invn) % m;
}
return;
}
void PolyMult(vector<int>&a, vector<int>&b, vector<int>&v, int m, int x)
{
int n = 1, sz = a.size() + b.size();
while (n < sz)n <<= 1;
vector<int>fa(a.begin(), a.end());
fa.resize(n, 0LL);
vector<int>fb(b.begin(), b.end());
fb.resize(n, 0LL);
int y = binpow(x, (m - 1) / n);
fft(fa, n, false, m, y);
fft(fb, n, false, m, y);
v.resize(n, 0LL);
for (int i = 0; i < n; i++)v[i] = (fa[i] * fb[i]) % m;
fft(v, n, true, m, y);
v.resize(sz - 1, 0LL);
return;
}
vector<int> solve1(int n, int x, vector<int>a)
{
vector<int>ans, arr;
int f[n + 1] = {0}, cc = 0;
vector<vector<int>>vec;
priority_queue<pair<int, int>>pq;
for (int i = 1; i <= n; i++)
{
if (a[i] >= x)a[i] = 1LL, cc++;
else a[i] = 0LL;
}
if (!cc)
{
for (int i = 1; i <= n; i++)ans.push_back(0LL);
return ans;
}
if (cc == 1)
{
ans.push_back(1LL);
for (int i = 1; i <= n; i++)ans.push_back(0LL);
return ans;
}
int prv = -1;
for (int i = 1; i <= n; i++)
{
if (a[i])
{
if (prv != -1)
f[i - prv]++;
prv = i;
}
}
for (int i = 1; i <= n; i++)
{
if (!f[i])continue;
vector<int>v;
for (int j = 0; j <= f[i]; j++)
{
int z = (binpow(i, j) * ncr(f[i], j)) % mod;
v.push_back(z);
}
arr = v;
vec.push_back(v);
pq.push({ -v.size(), vec.size() - 1});
}
while (pq.size() > 1)
{
int idx1 = pq.top().second;
pq.pop();
int idx2 = pq.top().second;
pq.pop();
if (idx1 > idx2)swap(idx1, idx2);
vector<int>v1 = vec[idx1];
vector<int>v2 = vec[idx2];
PolyMult(v1, v2, arr, mod, proot);
vec[idx1] = arr;
pq.push({ -ans.size(), idx1});
}
int sz = arr.size();
for (int i = 0; i < sz; i++)
{
if (i + 1 <= n)
ans.push_back(arr[i]);
}
for (int i = sz + 1; i <= n; i++)ans.push_back(0LL);
return ans;
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
precompute();
int t;
cin>>t;
assert(t >= 1 && t <= 70000);
while (t--)
{
int n, x;
cin>>n>>x;
assert(n >= 1 && n <= 1e6);
assert(x >= 1 && x <= 1e9);
vector<int>a(n + 1);
for (int i = 1; i <= n; i++)
{
cin>>a[i];
assert(a[i] >= 1 && a[i] <= 1e9);
}
vector<int>ans1 = solve1(n, x, a);
for (int i = 0; i < n; i++)
{
if (i == n - 1)cout<< ans1[i] << "\n";
else cout << ans1[i] << " ";
}
sum += n;
assert(sum >= 1 && sum <= 1e6);
}
return 0;
}
Tester's Solution
import java.util.*;
import java.io.*;
class ARRPART{
//SOLUTION BEGIN
long MOD = 998244353;
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), X = ni();
long[][] fif = fif(N);
boolean[] A = new boolean[N];
for(int i = 0; i< N; i++)A[i] = ni() >= X;
int[] cnt = new int[N];
for(int i = 0, ii = 0; i< N; i = ii){
while(i < N && !A[i])i++;
if(i == N)break;
ii = i+1;
while(ii < N && !A[ii])ii++;
if(ii == N)break;
cnt[ii-i]++;
i = ii;
}
PriorityQueue<long[]> pq = new PriorityQueue<>((long[] l1, long[] l2) -> Long.compare(l1.length, l2.length));
for(int i = 1; i< N; i++){
if(cnt[i] == 0)continue;
long[] cur = new long[1+cnt[i]];
for(int j = 0; j<= cnt[i]; j++)cur[j] = C(fif, cnt[i], j) * pow(i, j)%MOD;
pq.add(cur);
}
boolean OR = false;
for(boolean f:A)OR |= f;
if(OR)pq.add(new long[]{1});
else pq.add(new long[]{0});
while(pq.size() > 1)pq.add(Convolution.convolution(pq.poll(), pq.poll(), (int)MOD));
long[] ans = Arrays.copyOf(pq.poll(), N);
for(long x:ans)p(x+" ");pn("");
}
long[] mul(long[] a, long[] b){
long[] c = new long[a.length+b.length-1];
for(int i = 0; i< a.length; i++)
for(int j = 0; j< b.length; j++)
c[i+j] = (c[i+j]+a[i]*b[j])%MOD;
return c;
}
long pow(long a, long p){
long o = 1;
for(; p>0;p>>=1){
if((p&1)==1)o = o*a%MOD;
a = a*a%MOD;
}
return o;
}
long[][] fif(int mx){
mx++;
long[] F = new long[mx], IF = new long[mx];
F[0] = 1;
for(int i = 1; i< mx; i++)F[i] = (F[i-1]*i)%MOD;
//GFG
long M = MOD;
long y = 0, x = 1;
long a = F[mx-1];
while(a> 1){
long q = a/M;
long t = M;
M = a%M;
a = t;
t = y;
y = x-q*y;
x = t;
}
if(x<0)x+=MOD;
IF[mx-1] = x;
for(int i = mx-2; i>= 0; i--)IF[i] = (IF[i+1]*(i+1))%MOD;
return new long[][]{F, IF};
}
long C(long[][] fif, int n, int r){
if(n<r || r<0)return 0;
return (fif[0][n]*((fif[1][r]*fif[1][n-r])%MOD))%MOD;
}
/**
* Convolution.
*
* @verified https://atcoder.jp/contests/practice2/tasks/practice2_f
* @verified https://judge.yosupo.jp/problem/convolution_mod_1000000007
*/
static class Convolution {
/**
* Find a primitive root.
*
* @param m A prime number.
* @return Primitive root.
*/
private static int primitiveRoot(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int[] divs = new int[20];
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long) (i) * i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2; ; g++) {
boolean ok = true;
for (int i = 0; i < cnt; i++) {
if (pow(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
/**
* Power.
*
* @param x Parameter x.
* @param n Parameter n.
* @param m Mod.
* @return n-th power of x mod m.
*/
private static long pow(long x, long n, int m) {
if (m == 1) return 0;
long r = 1;
long y = x % m;
while (n > 0) {
if ((n & 1) != 0) r = (r * y) % m;
y = (y * y) % m;
n >>= 1;
}
return r;
}
/**
* Ceil of power 2.
*
* @param n Value.
* @return Ceil of power 2.
*/
private static int ceilPow2(int n) {
int x = 0;
while ((1L << x) < n) x++;
return x;
}
/**
* Garner's algorithm.
*
* @param c Mod convolution results.
* @param mods Mods.
* @return Result.
*/
private static long garner(long[] c, int[] mods) {
int n = c.length + 1;
long[] cnst = new long[n];
long[] coef = new long[n];
java.util.Arrays.fill(coef, 1);
for (int i = 0; i < n - 1; i++) {
int m1 = mods[i];
long v = (c[i] - cnst[i] + m1) % m1;
v = v * pow(coef[i], m1 - 2, m1) % m1;
for (int j = i + 1; j < n; j++) {
long m2 = mods[j];
cnst[j] = (cnst[j] + coef[j] * v) % m2;
coef[j] = (coef[j] * m1) % m2;
}
}
return cnst[n - 1];
}
/**
* Pre-calculation for NTT.
*
* @param mod NTT Prime.
* @param g Primitive root of mod.
* @return Pre-calculation table.
*/
private static long[] sumE(int mod, int g) {
long[] sum_e = new long[30];
long[] es = new long[30];
long[] ies = new long[30];
int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
long e = pow(g, (mod - 1) >> cnt2, mod);
long ie = pow(e, mod - 2, mod);
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e = e * e % mod;
ie = ie * ie % mod;
}
long now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_e[i] = es[i] * now % mod;
now = now * ies[i] % mod;
}
return sum_e;
}
/**
* Pre-calculation for inverse NTT.
*
* @param mod Mod.
* @param g Primitive root of mod.
* @return Pre-calculation table.
*/
private static long[] sumIE(int mod, int g) {
long[] sum_ie = new long[30];
long[] es = new long[30];
long[] ies = new long[30];
int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
long e = pow(g, (mod - 1) >> cnt2, mod);
long ie = pow(e, mod - 2, mod);
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e = e * e % mod;
ie = ie * ie % mod;
}
long now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_ie[i] = ies[i] * now % mod;
now = now * es[i] % mod;
}
return sum_ie;
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterflyInv(long[] a, long[] sumIE, int mod) {
int n = a.length;
int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
long inow = 1;
for (int s = 0; s < w; s++) {
int offset = s << (h - ph + 1);
for (int i = 0; i < p; i++) {
long l = a[i + offset];
long r = a[i + offset + p];
a[i + offset] = (l + r) % mod;
a[i + offset + p] = (mod + l - r) * inow % mod;
}
int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % mod;
}
}
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly(long[] a, long[] sumE, int mod) {
int n = a.length;
int h = ceilPow2(n);
for (int ph = 1; ph <= h; ph++) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
long now = 1;
for (int s = 0; s < w; s++) {
int offset = s << (h - ph + 1);
for (int i = 0; i < p; i++) {
long l = a[i + offset];
long r = a[i + offset + p] * now % mod;
a[i + offset] = (l + r) % mod;
a[i + offset + p] = (l - r + mod) % mod;
}
int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % mod;
}
}
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod NTT Prime.
* @return Answer.
*/
public static long[] convolution(long[] a, long[] b, int mod) {
int n = a.length;
int m = b.length;
if (n == 0 || m == 0) return new long[0];
int z = 1 << ceilPow2(n + m - 1);
{
long[] na = new long[z];
long[] nb = new long[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
int g = primitiveRoot(mod);
long[] sume = sumE(mod, g);
long[] sumie = sumIE(mod, g);
butterfly(a, sume, mod);
butterfly(b, sume, mod);
for (int i = 0; i < z; i++) {
a[i] = a[i] * b[i] % mod;
}
butterflyInv(a, sumie, mod);
a = java.util.Arrays.copyOf(a, n + m - 1);
long iz = pow(z, mod - 2, mod);
for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % mod;
return a;
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Any mod.
* @return Answer.
*/
public static long[] convolutionLL(long[] a, long[] b, int mod) {
int n = a.length;
int m = b.length;
if (n == 0 || m == 0) return new long[0];
int mod1 = 754974721;
int mod2 = 167772161;
int mod3 = 469762049;
long[] c1 = convolution(a, b, mod1);
long[] c2 = convolution(a, b, mod2);
long[] c3 = convolution(a, b, mod3);
int retSize = c1.length;
long[] ret = new long[retSize];
int[] mods = {mod1, mod2, mod3, mod};
for (int i = 0; i < retSize; ++i) {
ret[i] = garner(new long[]{c1[i], c2[i], c3[i]}, mods);
}
return ret;
}
/**
* Naive convolution. (Complexity is O(N^2)!!)
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Mod.
* @return Answer.
*/
public static long[] convolutionNaive(long[] a, long[] b, int mod) {
int n = a.length;
int m = b.length;
int k = n + m - 1;
long[] ret = new long[k];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ret[i + j] += a[i] * b[j] % mod;
ret[i + j] %= mod;
}
}
return ret;
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new ARRPART().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}