#include <bits/stdc++.h>
using namespace std;

// ===================================================================
// This file contains a collection of Fast Fourier Transform (FFT) and
// Number Theoretic Transform (NTT) algorithms. Each function is ready
// to be used as a "black box".
// Read the comments above each one to understand:
//   - What it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
// ===================================================================

// ===================================================================
// 1) Core NTT (Number Theoretic Transform) Implementation
//    NTT is the modular arithmetic version of FFT. It computes the
//    exact convolution of two integer sequences modulo a prime number.
//    This is the foundation for almost all functions in this file.
//    Think of it as: given two polynomials, NTT multiplies them very fast.
// ===================================================================

// NTT-friendly primes and their primitive roots.
// A "primitive root" is a special number that generates all non-zero
// elements of the finite field when raised to different powers.
// The modulus must be of the form: mod = c * 2^k + 1, where k is large
// enough to support the transform length.
const int MOD = 998244353;        // = 119 * 2^23 + 1, primitive root = 3
const int MOD2 = 1004535809;      // = 479 * 2^21 + 1, primitive root = 3
const int MOD3 = 469762049;       // = 7 * 2^26 + 1, primitive root = 3
const int PRIMITIVE_ROOT = 3;

// 1.1) Modular exponentiation (fast power).
//      This is a helper function used internally by NTT.
//      Parameters:
//        - a: base (long long)
//        - e: exponent (long long)
//        - mod: modulus (long long)
//      Returns:
//        - a^e % mod
//      Time complexity: O(log e)
//      Constraint: mod > 0.
long long modpow(long long a, long long e, long long mod) {
    long long r = 1;
    while (e) {
        if (e & 1) r = (r * a) % mod;
        a = (a * a) % mod;
        e >>= 1;
    }
    return r;
}

// 1.2) Generic NTT (works with any NTT‑friendly modulus and primitive root).
//      This is the core transform function. It converts a polynomial from
//      coefficient form to point-value form (or vice versa) using the
//      NTT algorithm.
//      Think of it as a fast way to evaluate a polynomial at many points.
//      Parameters:
//        - a: vector of integers (the polynomial coefficients). This vector
//             is modified in-place.
//        - invert: boolean. If false, performs forward NTT.
//                  If true, performs inverse NTT.
//        - mod: the prime modulus (must be NTT‑friendly).
//        - root: the primitive root modulo 'mod'.
//      Returns:
//        - Nothing (the result is stored in the input vector 'a').
//      Time complexity: O(n log n), where n = a.size()
//      Important constraints:
//        - The length of 'a' (n) MUST be a power of two.
//        - All coefficients must be in the range [0, mod-1].
//      Note: This function uses the iterative Cooley-Tukey algorithm.
void ntt_generic(vector<int>& a, bool invert, int mod, int root) {
    int n = (int)a.size();

    // Bit-reversal permutation.
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        int wlen = modpow(root, (mod - 1) / len, mod);
        if (invert) wlen = modpow(wlen, mod - 2, mod);

        for (int i = 0; i < n; i += len) {
            long long w = 1;
            for (int j = 0; j < len / 2; j++) {
                int u = a[i + j];
                int v = (int)(a[i + j + len / 2] * w % mod);

                a[i + j] = u + v;
                if (a[i + j] >= mod) a[i + j] -= mod;

                a[i + j + len / 2] = u - v;
                if (a[i + j + len / 2] < 0) a[i + j + len / 2] += mod;

                w = w * wlen % mod;
            }
        }
    }

    if (invert) {
        int n_inv = modpow(n, mod - 2, mod);
        for (int &x : a) x = (int)((long long)x * n_inv % mod);
    }
}

// 1.3) NTT Convolution with a specified modulus and primitive root.
//      Multiplies two polynomials modulo a given NTT-friendly prime.
//      Parameters:
//        - a, b: vectors of coefficients (values in [0, mod-1]).
//        - mod: the NTT-friendly modulus.
//        - root: the primitive root modulo 'mod'.
//      Returns:
//        - A vector of integers representing (a * b) modulo 'mod'.
//      Time complexity: O(n log n) where n is the padded size.
vector<int> convolution_mod(const vector<int>& a, const vector<int>& b, int mod, int root) {
    int n = (int)a.size(), m = (int)b.size();
    if (!n || !m) return {};

    int sz = 1;
    while (sz < n + m - 1) sz <<= 1;

    vector<int> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(sz);
    fb.resize(sz);

    ntt_generic(fa, false, mod, root);
    ntt_generic(fb, false, mod, root);

    for (int i = 0; i < sz; i++) {
        fa[i] = (int)((long long)fa[i] * fb[i] % mod);
    }

    ntt_generic(fa, true, mod, root);
    fa.resize(n + m - 1);
    return fa;
}

// 1.4) Default NTT Convolution (using the global MOD = 998244353).
//      This is the simplest version; use it when your modulus is 998244353.
vector<int> convolution(const vector<int>& a, const vector<int>& b) {
    return convolution_mod(a, b, MOD, PRIMITIVE_ROOT);
}

// 1.5) Arbitrary Modulus Convolution (using CRT with 3 NTT-friendly primes).
//      This function multiplies two polynomials modulo an arbitrary integer 'mod'.
//      It uses three NTT-friendly primes and combines the results via Garner's algorithm.
//      Parameters:
//        - a, b: vectors of coefficients (values in [0, mod-1]).
//        - mod: the target modulus (can be any positive integer).
//      Returns:
//        - A vector of integers representing (a * b) modulo 'mod'.
//      Time complexity: O(n log n) with a constant factor (~3x slower).
//      Important constraints:
//        - The product of the three primes is > 1e27, which is large enough for
//          most practical ranges to avoid ambiguity.
vector<int> convolutionArbitraryMod(const vector<int>& a, const vector<int>& b, int mod) {
    const int m1 = 998244353, m2 = 1004535809, m3 = 469762049;
    const int r1 = 3, r2 = 3, r3 = 3;

    auto c1 = convolution_mod(a, b, m1, r1);
    auto c2 = convolution_mod(a, b, m2, r2);
    auto c3 = convolution_mod(a, b, m3, r3);

    int n = (int)c1.size();
    vector<int> res(n);

    // Precompute inverses for Garner's algorithm.
    static const long long inv_m1_m2 = modpow(m1, m2 - 2, m2);
    static const long long inv_m1m2_m3 = modpow((long long)m1 * m2 % m3, m3 - 2, m3);

    for (int i = 0; i < n; i++) {
        long long x1 = c1[i];
        long long t1 = ((c2[i] - x1) % m2 + m2) % m2;
        t1 = t1 * inv_m1_m2 % m2;
        long long x2 = x1 + (long long)m1 * t1;

        long long t2 = ((c3[i] - x2) % m3 + m3) % m3;
        t2 = t2 * inv_m1m2_m3 % m3;
        long long x3 = x2 + (long long)m1 * m2 % mod * t2 % mod;

        res[i] = (int)(x3 % mod);
    }

    return res;
}

// ===================================================================
// 2) FFT (Fast Fourier Transform) with Complex Numbers
//    FFT uses complex numbers and works for any real/integer input.
//    It is more flexible than NTT (no modulus restrictions) but can
//    have precision issues with very large numbers.
// ===================================================================

using cd = complex<double>;
const double PI = acos(-1);

// 2.1) Iterative FFT.
//      This is the complex-number version of the transform.
//      Parameters:
//        - a: vector of complex numbers. Modified in-place.
//        - invert: boolean. If false, forward transform. If true, inverse.
//      Returns:
//        - Nothing (result stored in 'a').
//      Time complexity: O(n log n), where n = a.size()
//      Important constraints:
//        - The length of 'a' MUST be a power of two.
//      Note: Uses complex numbers and may have precision errors.
void fft(vector<cd>& a, bool invert) {
    int n = a.size();

    // Bit-reversal permutation.
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));

        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i + j];
                cd v = a[i + j + len / 2] * w;

                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;

                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd &x : a) x /= n;
    }
}

// 2.2) FFT Convolution (polynomial multiplication with real numbers).
//      Multiplies two polynomials using FFT with complex numbers.
//      Parameters:
//        - a: vector of integers (coefficients of the first polynomial)
//        - b: vector of integers (coefficients of the second polynomial)
//      Returns:
//        - A vector of long long integers (rounded from the complex result).
//      Time complexity: O(n log n), where n is the power-of-two size.
//      Important constraints:
//        - The result is rounded to the nearest integer. Precision errors
//          can occur if the coefficients are very large ( > 1e9 ) or the
//          polynomial degree is very high.
//        - Use this when you don't have an NTT-friendly modulus or when
//          you need the exact integer result (not modulo).
vector<long long> convolutionFFT(const vector<int>& a, const vector<int>& b) {
    int n = a.size(), m = b.size();
    if (!n || !m) return {};

    int sz = 1;
    while (sz < n + m - 1) sz <<= 1;

    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(sz);
    fb.resize(sz);

    fft(fa, false);
    fft(fb, false);

    for (int i = 0; i < sz; i++) {
        fa[i] *= fb[i];
    }

    fft(fa, true);

    vector<long long> res(n + m - 1);
    const double EPS = 1e-9;
    for (int i = 0; i < n + m - 1; i++) {
        res[i] = (long long)round(fa[i].real() + EPS);
    }

    return res;
}

// ===================================================================
// 3) Common Problems Solved with FFT/NTT
//    These are patterns that frequently appear in ECPC/ACPC problems.
//    The idea is to convert the problem into a convolution.
// ===================================================================

// 3.1) Counting all pair sums.
//      Given an array of integers, count how many pairs (i, j) have a
//      sum equal to each possible value.
//      Parameters:
//        - arr: vector of integers (the input array)
//      Returns:
//        - A vector 'res' where res[s] = number of ordered pairs with sum = s.
//      Time complexity: O(n log n), where n = max_value - min_value.
//      Important constraints:
//        - The array values must be non-negative. If they can be negative,
//          shift them by the minimum value to make them non-negative.
//        - The result counts ordered pairs (i, j) including i=j.
//          If you need unordered pairs (i < j), adjust the result.
vector<long long> countPairSums(const vector<int>& arr) {
    if (arr.empty()) return {};

    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());

    int shift = -minVal;
    int size = maxVal - minVal + 1;

    vector<int> freq(size, 0);
    for (int x : arr) {
        freq[x + shift]++;
    }

    vector<long long> conv = convolutionFFT(freq, freq);
    vector<long long> result(2 * size - 1, 0);
    for (int s = 0; s < (int)conv.size(); s++) {
        int sum = s - 2 * shift;
        if (0 <= sum && sum < (int)result.size()) {
            result[sum] = conv[s];
        }
    }
    return result;
}

// 3.2) Counting all pair differences.
//      Given an array of integers, count how many ordered pairs (i, j)
//      have a difference arr[i] - arr[j] equal to each possible value.
//      Parameters:
//        - arr: vector of integers (the input array)
//      Returns:
//        - A vector 'res' where res[d] = number of ordered pairs with difference = d.
//      Time complexity: O(n log n), where n = max_value - min_value.
vector<long long> countPairDifferences(const vector<int>& arr) {
    if (arr.empty()) return {};

    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());

    int shift = -minVal;
    int size = maxVal - minVal + 1;

    vector<int> freq(size, 0);
    for (int x : arr) {
        freq[x + shift]++;
    }

    vector<int> revFreq = freq;
    reverse(revFreq.begin(), revFreq.end());

    vector<long long> conv = convolutionFFT(freq, revFreq);
    vector<long long> result(2 * size - 1, 0);
    for (int idx = 0; idx < (int)conv.size(); idx++) {
        int diff = idx - (size - 1);
        if (0 <= diff && diff < (int)result.size()) {
            result[diff] = conv[idx];
        }
    }
    return result;
}

// 3.3) Counting all subarray sums (for non‑negative arrays).
//      Given an array of non‑negative integers, count how many subarrays
//      have each possible sum.
//      Parameters:
//        - arr: vector of non‑negative integers.
//      Returns:
//        - A vector 'res' where res[s] = number of subarrays with sum = s.
//      Time complexity: O(T log T) where T = total sum of the array.
//      Important constraints:
//        - All elements MUST be non‑negative. The method does not work
//          with negative numbers because prefix sums are not monotonic.
vector<long long> countSubarraySums(const vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return {};

    // Check non‑negativity.
    for (int x : arr) {
        if (x < 0) return {}; // Not supported.
    }

    int totalSum = accumulate(arr.begin(), arr.end(), 0);

    vector<int> prefFreq(totalSum + 1, 0);
    prefFreq[0] = 1; // empty prefix
    int pref = 0;
    for (int x : arr) {
        pref += x;
        prefFreq[pref]++;
    }

    // We need sum_{i} freq[i] * freq[i+S] for each S.
    // This is cross‑correlation. Let revFreq[j] = freq[totalSum - j].
    // Then (freq * revFreq)[totalSum - S] = sum_i freq[i] * freq[i+S].
    vector<int> revFreq = prefFreq;
    reverse(revFreq.begin(), revFreq.end());

    vector<long long> conv = convolutionFFT(prefFreq, revFreq);
    vector<long long> result(totalSum + 1, 0);

    for (int S = 0; S <= totalSum; S++) {
        int idx = totalSum - S;
        if (0 <= idx && idx < (int)conv.size()) {
            result[S] = conv[idx];
        }
        // For S = 0, result[0] = sum_i freq[i]^2 (ordered pairs including i=j).
        // Number of subarrays with sum 0 is sum_i C(freq[i], 2) = (sum_i freq[i]^2 - (n+1)) / 2.
        // We adjust here.
        if (S == 0) {
            long long ordered = result[0];
            long long totalPref = n + 1; // number of prefix sums
            result[0] = (ordered - totalPref) / 2;
        }
    }

    return result;
}

// 3.4) String matching with wildcards (e.g., '*' matches any character).
//      Given a text string and a pattern string that may contain wildcards,
//      find all positions in the text where the pattern matches.
//      Parameters:
//        - text: the text string (lowercase letters)
//        - pattern: the pattern string (lowercase letters and '*' wildcard)
//      Returns:
//        - A vector of indices (0-based) where the pattern matches.
//      Time complexity: O((n+m) log (n+m)) * alphabet_size
//      Important constraints:
//        - The strings should contain only lowercase letters and '*'.
//        - The wildcard '*' matches any single character.
vector<int> wildcardMatching(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    if (m > n) return {};

    const int ALPHA = 26;
    vector<int> matches(n - m + 1, 0);

    for (char c = 'a'; c <= 'z'; c++) {
        vector<int> A(n, 0), B(m, 0);
        for (int i = 0; i < n; i++) {
            if (text[i] == c) A[i] = 1;
        }
        for (int j = 0; j < m; j++) {
            if (pattern[j] == c || pattern[j] == '*') B[j] = 1;
        }

        reverse(B.begin(), B.end());
        vector<long long> conv = convolutionFFT(A, B);

        for (int i = 0; i <= n - m; i++) {
            matches[i] += conv[i + m - 1];
        }
    }

    int required = 0;
    for (char ch : pattern) {
        if (ch != '*') required++;
    }

    vector<int> result;
    for (int i = 0; i <= n - m; i++) {
        if (matches[i] == required) result.push_back(i);
    }
    return result;
}

// 3.5) Multiplying large integers (Big Integer multiplication).
//      Given two large integers as strings, multiply them.
//      Parameters:
//        - a: string representing the first integer
//        - b: string representing the second integer
//      Returns:
//        - A string representing the product.
//      Time complexity: O(n log n), where n = max(len(a), len(b)).
//      Important constraints:
//        - The input strings should only contain digits (0-9).
string multiplyBigIntegers(const string& a, const string& b) {
    if (a == "0" || b == "0") return "0";

    int n = a.size(), m = b.size();
    vector<int> A(n), B(m);

    for (int i = 0; i < n; i++) A[i] = a[n - 1 - i] - '0';
    for (int i = 0; i < m; i++) B[i] = b[m - 1 - i] - '0';

    vector<long long> conv = convolutionFFT(A, B);

    vector<int> res(conv.size() + 1, 0);
    for (int i = 0; i < (int)conv.size(); i++) {
        res[i] += conv[i];
        res[i + 1] += res[i] / 10;
        res[i] %= 10;
    }

    while (res.size() > 1 && res.back() == 0) res.pop_back();

    string ans;
    for (int i = (int)res.size() - 1; i >= 0; i--) {
        ans.push_back(char('0' + res[i]));
    }
    return ans;
}

// ===================================================================
// 4) Advanced Techniques (Formal Power Series)
//    These are more sophisticated operations that appear in harder problems.
// ===================================================================

// 4.1) Online NTT (Divide and Conquer DP optimization).
//      Used when dp[i] depends on previous dp values through a convolution.
//      Example: dp[i] = sum_{j < i} dp[j] * f[i-j].
//      This can be computed in O(n log^2 n) using divide and conquer + NTT.
//      Parameters:
//        - dp: vector to be filled (dp[0] should be initialized)
//        - f: the convolution kernel (f[0] is usually 0)
//        - n: number of terms to compute
//      Returns:
//        - Nothing (dp is modified in-place).
//      Time complexity: O(n log^2 n)
//      Important constraints:
//        - dp[0] must be set before calling this function.
//        - The result is computed modulo MOD.
void onlineNTT(vector<int>& dp, const vector<int>& f, int n) {
    function<void(int,int)> solve = [&](int l, int r) {
        if (l == r) return;
        int mid = (l + r) / 2;
        solve(l, mid);

        int len1 = mid - l + 1;
        int len2 = r - mid;
        vector<int> A(len1), B(len1 + len2 - 1);

        for (int i = l; i <= mid; i++) A[i - l] = dp[i];
        for (int i = 0; i < len1 + len2 - 1; i++) {
            B[i] = (i < (int)f.size() ? f[i] : 0);
        }

        vector<int> C = convolution(A, B);
        for (int i = mid + 1; i <= r; i++) {
            dp[i] = (dp[i] + C[i - l]) % MOD;
        }

        solve(mid + 1, r);
    };

    solve(0, n - 1);
}

// 4.2) Polynomial Inverse (formal power series inverse).
//      Given a polynomial A(x), compute its inverse modulo x^n.
//      That is, find B(x) such that A(x) * B(x) ≡ 1 (mod x^n).
//      Parameters:
//        - a: vector of coefficients of A (a[0] must be non‑zero)
//        - n: the number of terms to compute
//      Returns:
//        - A vector of length n representing the inverse polynomial.
//      Time complexity: O(n log n)
//      Important constraints:
//        - a[0] must be invertible modulo MOD.
//        - The result is computed modulo MOD.
vector<int> polynomialInverse(const vector<int>& a, int n) {
    vector<int> res(1, modpow(a[0], MOD - 2, MOD));
    int cur = 1;

    while (cur < n) {
        int next = min(cur * 2, n);
        vector<int> f(a.begin(), a.begin() + min((int)a.size(), next));
        vector<int> g = res;

        f.resize(next);
        g.resize(next);

        vector<int> fg = convolution(f, g);
        fg.resize(next);

        for (int i = 0; i < next; i++) {
            fg[i] = (MOD - fg[i]) % MOD;
        }
        fg[0] = (fg[0] + 2) % MOD;

        res = convolution(g, fg);
        res.resize(next);
        cur = next;
    }

    res.resize(n);
    return res;
}

// 4.3) Polynomial Logarithm (log of a formal power series).
//      Computes log(A(x)) modulo x^n.
//      Parameters:
//        - a: vector of coefficients of A (a[0] must be 1)
//        - n: the number of terms to compute
//      Returns:
//        - A vector of length n representing log(A(x)).
//      Time complexity: O(n log n)
//      Important constraints:
//        - a[0] must be 1.
//        - The result is computed modulo MOD.
vector<int> polynomialLog(const vector<int>& a, int n) {
    vector<int> der(max(0, (int)a.size() - 1));
    for (int i = 1; i < (int)a.size(); i++) {
        der[i - 1] = (long long)a[i] * i % MOD;
    }

    vector<int> inv = polynomialInverse(a, n);
    vector<int> prod = convolution(der, inv);
    prod.resize(n);

    vector<int> res(n, 0);
    for (int i = 1; i < n; i++) {
        res[i] = (long long)prod[i - 1] * modpow(i, MOD - 2, MOD) % MOD;
    }
    return res;
}

// 4.4) Polynomial Exponential (exp of a formal power series).
//      Computes exp(A(x)) modulo x^n.
//      Parameters:
//        - a: vector of coefficients of A (a[0] must be 0)
//        - n: the number of terms to compute
//      Returns:
//        - A vector of length n representing exp(A(x)).
//      Time complexity: O(n log n)
//      Important constraints:
//        - a[0] must be 0.
vector<int> polynomialExp(const vector<int>& a, int n) {
    vector<int> res(1, 1);
    int cur = 1;

    while (cur < n) {
        int next = min(cur * 2, n);
        vector<int> logRes = polynomialLog(res, next);
        vector<int> diff(next, 0);

        for (int i = 0; i < next; i++) {
            diff[i] = (a[i] - logRes[i] + MOD) % MOD;
        }
        diff[0] = (diff[0] + 1) % MOD;

        res = convolution(res, diff);
        res.resize(next);
        cur = next;
    }

    res.resize(n);
    return res;
}

// 4.5) Polynomial Power (raising a polynomial to a power).
//      Computes A(x)^k modulo x^n efficiently.
//      Parameters:
//        - a: vector of coefficients of A(x).
//        - k: the exponent (can be a long long).
//        - n: the number of terms to compute.
//      Returns:
//        - A vector of length n representing A(x)^k.
//      Time complexity: O(n log n)
//      Important constraints:
//        - If a[0] != 0, uses exp(k * log(A)).
//        - If a[0] == 0, it shifts the polynomial to make the first term non-zero.
vector<int> polynomialPower(const vector<int>& a, long long k, int n) {
    int shift = 0;
    while (shift < (int)a.size() && a[shift] == 0) shift++;

    if (shift == (int)a.size()) {
        return vector<int>(n, 0);
    }

    if ((long long)shift * k >= n) {
        return vector<int>(n, 0);
    }

    vector<int> b(a.begin() + shift, a.end());
    int leading = b[0];

    int invLeading = modpow(leading, MOD - 2, MOD);
    for (int &x : b) {
        x = (long long)x * invLeading % MOD;
    }

    vector<int> logB = polynomialLog(b, n - shift * k);
    for (int &x : logB) {
        x = (long long)x * (k % MOD) % MOD;
    }

    vector<int> expLog = polynomialExp(logB, n - shift * k);

    int leadingPow = modpow(leading, k, MOD);
    vector<int> res(n, 0);
    for (int i = 0; i < (int)expLog.size(); i++) {
        res[i + shift * k] = (long long)expLog[i] * leadingPow % MOD;
    }

    return res;
}

// 4.6) Polynomial Square Root.
//      Computes sqrt(A(x)) modulo x^n.
//      Parameters:
//        - a: vector of coefficients of A(x). a[0] must be a quadratic residue.
//        - n: the number of terms to compute.
//      Returns:
//        - A vector of length n representing sqrt(A(x)).
//      Time complexity: O(n log n)
//      Important constraints:
//        - Assumes a[0] = 1 (most common case). For a general a[0], you need
//          to compute its square root modulo MOD.
vector<int> polynomialSqrt(const vector<int>& a, int n) {
    const int INV2 = (MOD + 1) / 2; // modular inverse of 2
    vector<int> res(1, 1); // sqrt(1) = 1
    int cur = 1;

    while (cur < n) {
        int next = min(cur * 2, n);
        vector<int> f(a.begin(), a.begin() + min((int)a.size(), next));
        f.resize(next);

        vector<int> invRes = polynomialInverse(res, next);

        vector<int> prod = convolution(f, invRes);
        prod.resize(next);

        for (int i = 0; i < next; i++) {
            res[i] = (long long)(res[i] + prod[i]) * INV2 % MOD;
        }
        res.resize(next);
        cur = next;
    }

    res.resize(n);
    return res;
}

// ===================================================================
// 5) Utility functions for working with polynomials.
// ===================================================================

// 5.1) Trim a polynomial (remove trailing zeros).
vector<int> trimPoly(const vector<int>& a) {
    vector<int> res = a;
    while (!res.empty() && res.back() == 0) res.pop_back();
    if (res.empty()) res.push_back(0);
    return res;
}

// 5.2) Evaluate a polynomial at a point x.
long long evalPoly(const vector<int>& a, long long x) {
    long long res = 0;
    for (int i = (int)a.size() - 1; i >= 0; i--) {
        res = (res * x + a[i]) % MOD;
    }
    return res;
}

// 5.3) Derivative of a polynomial.
vector<int> derivative(const vector<int>& a) {
    if (a.size() <= 1) return {0};
    vector<int> res(a.size() - 1);
    for (int i = 1; i < (int)a.size(); i++) {
        res[i - 1] = (long long)a[i] * i % MOD;
    }
    return res;
}

// 5.4) Integral of a polynomial (constant term is 0).
vector<int> integral(const vector<int>& a) {
    vector<int> res(a.size() + 1, 0);
    for (int i = 0; i < (int)a.size(); i++) {
        res[i + 1] = (long long)a[i] * modpow(i + 1, MOD - 2, MOD) % MOD;
    }
    return res;
}

// ===================================================================
// 6) Summary of when to use FFT vs NTT
//    - Use FFT (complex numbers) when:
//        * You need the exact integer result (not modulo).
//        * The coefficients are small enough to avoid precision errors.
//        * The modulus is not NTT-friendly.
//    - Use NTT (modular arithmetic) when:
//        * You need the result modulo a prime.
//        * The modulus is NTT-friendly (e.g., 998244353).
//        * You want exact results without precision issues.
//    - Use Arbitrary Modulus Convolution when:
//        * The modulus is not NTT-friendly but you need exact results.
//        * The modulus is up to ~1e9.
// ===================================================================

// ===================================================================
// main() with example usage (you can ignore this part)
// ===================================================================

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example 1: Polynomial multiplication.
    vector<int> a = {1, 2, 3}; // 1 + 2x + 3x^2
    vector<int> b = {4, 5};    // 4 + 5x
    vector<int> c = convolution(a, b);
    // Expected: 4 + 13x + 22x^2 + 15x^3

    cout << "Convolution result: ";
    for (int x : c) cout << x << " ";
    cout << "\n";

    // Example 2: Big integer multiplication.
    string bigA = "123456789";
    string bigB = "987654321";
    string product = multiplyBigIntegers(bigA, bigB);
    cout << bigA << " * " << bigB << " = " << product << "\n";

    // Example 3: Wildcard matching.
    string text = "abcde";
    string pattern = "a*e";
    vector<int> matches = wildcardMatching(text, pattern);
    cout << "Wildcard matches at positions: ";
    for (int pos : matches) cout << pos << " ";
    cout << "\n";

    return 0;
}