代码

#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string.h>
#include <type_traits>
#include <unordered_map>
#include <cstdint>
#include <vector>
#include <utility>
namespace OY {
#define cin OY::inputHelper<1 << 18, 20>::getInstance()
#define getchar() ({char c=cin.getChar_Checked();cin.next();c; })
#define cout OY::outputHelper<1 << 18>::getInstance()
#define putchar cout.putChar
#define endl '\n'
#define putlog(...) OY::printLog(", ", __VA_ARGS__)
template <uint64_t _BufferSize = 1 << 18, uint64_t _BlockSize = 20>
class inputHelper {
public:
    FILE *m_filePtr;
    char m_buf[_BufferSize], *m_end, *m_cursor;
    bool m_ok;
    void flush() {
        uint64_t a = m_end - m_cursor;
        if (a >= _BlockSize) return;
        memmove(m_buf, m_cursor, a);
        uint64_t b = fread(m_buf + a, 1, _BufferSize - a, m_filePtr);
        m_cursor = m_buf;
        if (a + b < _BufferSize) {
            m_end = m_buf + a + b;
            *m_end = EOF;
        }
    }
public:
    explicit inputHelper(const char *inputFileName) : m_ok(true) {
        if (!*inputFileName) m_filePtr = stdin;
        else m_filePtr = fopen(inputFileName, "rt");
        m_end = m_cursor = m_buf + _BufferSize;
    }
    ~inputHelper() { fclose(m_filePtr); }
    static inputHelper<_BufferSize, _BlockSize> &getInstance() {
        static inputHelper<_BufferSize, _BlockSize> s_obj("");
        return s_obj;
    }
    static constexpr bool isBlank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }
    static constexpr bool isEndline(char c) { return c == '\n' || c == EOF; }
    const char &getChar_Checked() {
        if (m_cursor < m_end) return *m_cursor;
        uint64_t b = fread(m_buf, 1, _BufferSize, m_filePtr);
        m_cursor = m_buf;
        if (b < _BufferSize) {
            m_end = m_buf + b;
            *m_end = EOF;
        }
        return *m_cursor;
    }
    const char &getChar_Unchecked() const { return *m_cursor; }
    void next() { ++m_cursor; }
    void setState(bool _ok) { m_ok = _ok; }
    template <typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
    inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
        while (isBlank(getChar_Checked())) next();
        flush();
        if (getChar_Unchecked() == '-') {
            next();
            if (isdigit(getChar_Unchecked())) {
                ret = -(getChar_Unchecked() - '0');
                while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 - (getChar_Unchecked() - '0');
            }
            else m_ok = false;
        }
        else {
            if (isdigit(getChar_Unchecked())) {
                ret = getChar_Unchecked() - '0';
                while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
            }
            else m_ok = false;
        }
        return *this;
    }
    template <typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
    inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
        while (isBlank(getChar_Checked())) next();
        flush();
        if (isdigit(getChar_Unchecked())) {
            ret = getChar_Unchecked() - '0';
            while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
        }
        else m_ok = false;
        return *this;
    }
    template <typename _Tp, typename std::enable_if<std::is_floating_point<_Tp>::value>::type * = nullptr>
    inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
        bool neg = false, integer = false, decimal = false;
        while (isBlank(getChar_Checked())) next();
        flush();
        if (getChar_Unchecked() == '-') {
            neg = true;
            next();
        }
        if (!isdigit(getChar_Unchecked()) && getChar_Unchecked() != '.') {
            m_ok = false;
            return *this;
        }
        if (isdigit(getChar_Unchecked())) {
            integer = true;
            ret = getChar_Unchecked() - '0';
            while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
        }
        if (getChar_Unchecked() == '.') {
            next();
            if (isdigit(getChar_Unchecked())) {
                if (!integer) ret = 0;
                decimal = true;
                _Tp unit = 0.1;
                ret += unit * (getChar_Unchecked() - '0');
                while (next(), isdigit(getChar_Unchecked())) {
                    unit *= 0.1;
                    ret += unit * (getChar_Unchecked() - '0');
                }
            }
        }
        if (!integer && !decimal) m_ok = false;
        else if (neg) ret = -ret;
        return *this;
    }
    inputHelper<_BufferSize, _BlockSize> &operator>>(char &ret) {
        while (isBlank(getChar_Checked())) next();
        ret = getChar_Checked();
        if (ret == EOF) m_ok = false;
        else next();
        return *this;
    }
    inputHelper<_BufferSize, _BlockSize> &operator>>(std::string &ret) {
        while (isBlank(getChar_Checked())) next();
        if (getChar_Checked() != EOF) {
            ret.clear();
            do {
                ret += getChar_Checked();
                next();
            } while (!isBlank(getChar_Checked()) && getChar_Unchecked() != EOF);
        }
        else m_ok = false;
        return *this;
    }
    explicit operator bool() { return m_ok; }
};
template <uint64_t _BufferSize = 1 << 20>
class outputHelper {
    FILE *m_filePtr = nullptr;
    char m_buf[_BufferSize], *m_end, *m_cursor;
    char m_tempBuf[50], *m_tempBufCursor, *m_tempBufDot;
    uint64_t m_floatReserve, m_floatRatio;
public:
    outputHelper(const char *outputFileName, int prec = 6) : m_end(m_buf + _BufferSize) {
        if (!*outputFileName) m_filePtr = stdout;
        else m_filePtr = fopen(outputFileName, "wt");
        m_cursor = m_buf;
        m_tempBufCursor = m_tempBuf;
        precision(prec);
    }
    static outputHelper<_BufferSize> &getInstance() {
        static outputHelper<_BufferSize> s_obj("");
        return s_obj;
    }
    ~outputHelper() {
        flush();
        fclose(m_filePtr);
    }
    void precision(int prec) {
        m_floatReserve = prec;
        m_floatRatio = pow(10, prec);
        m_tempBufDot = m_tempBuf + prec;
    }
    outputHelper<_BufferSize> &flush() {
        fwrite(m_buf, 1, m_cursor - m_buf, m_filePtr);
        fflush(m_filePtr);
        m_cursor = m_buf;
        return *this;
    }
    void putChar(const char &c) {
        if (m_cursor == m_end) flush();
        *m_cursor++ = c;
    }
    void putS(const char *c) { while (*c) putChar(*c++); }
    template <typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
    outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
        _Tp _ret = _Tp(ret);
        if (_ret >= 0) {
            do {
                *m_tempBufCursor++ = '0' + _ret % 10;
                _ret /= 10;
            } while (_ret);
            do putChar(*--m_tempBufCursor);
            while (m_tempBufCursor > m_tempBuf);
        }
        else {
            putChar('-');
            do {
                *m_tempBufCursor++ = '0' - _ret % 10;
                _ret /= 10;
            } while (_ret);
            do putChar(*--m_tempBufCursor);
            while (m_tempBufCursor > m_tempBuf);
        }
        return *this;
    }
    template <typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
    outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
        _Tp _ret = _Tp(ret);
        do {
            *m_tempBufCursor++ = '0' + _ret % 10;
            _ret /= 10;
        } while (_ret);
        do putChar(*--m_tempBufCursor);
        while (m_tempBufCursor > m_tempBuf);
        return *this;
    }
    template <typename _Tp, typename std::enable_if<std::is_floating_point<_Tp>::value>::type * = nullptr>
    outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
        if (ret < 0) {
            putChar('-');
            return *this << -ret;
        }
        _Tp _ret = ret * m_floatRatio;
        uint64_t integer = _ret;
        if (_ret - integer >= 0.4999999999) integer++;
        do {
            *m_tempBufCursor++ = '0' + integer % 10;
            integer /= 10;
        } while (integer);
        if (m_tempBufCursor > m_tempBufDot) {
            do putChar(*--m_tempBufCursor);
            while (m_tempBufCursor > m_tempBufDot);
            putChar('.');
        }
        else {
            putS("0.");
            for (int i = m_tempBufDot - m_tempBufCursor; i--;) putChar('0');
        }
        do putChar(*--m_tempBufCursor);
        while (m_tempBufCursor > m_tempBuf);
        return *this;
    }
    outputHelper<_BufferSize> &operator<<(const char &ret) {
        putChar(ret);
        return *this;
    }
    outputHelper<_BufferSize> &operator<<(const std::string &ret) {
        putS(ret.data());
        return *this;
    }
};
template <uint64_t _BufferSize, uint64_t _BlockSize>
inputHelper<_BufferSize, _BlockSize> &getline(inputHelper<_BufferSize, _BlockSize> &ih, std::string &ret) {
    ret.clear();
    if (ih.getChar_Checked() == EOF) ih.setState(false);
    else {
        while (!inputHelper<_BufferSize, _BlockSize>::isEndline(ih.getChar_Checked())) {
            ret += ih.getChar_Unchecked();
            ih.next();
        }
        ih.next();
    }
    return ih;
}
template <typename D, typename T, typename... S>
void printLog(D delim, const T &x, S... rest) {
    cout << x;
    if (sizeof...(rest) > 0) {
        cout << delim;
        printLog(delim, rest...);
    }
}
}
using OY::getline;
namespace OY {
template <typename _ModType, _ModType _P>
struct Modular {
    static constexpr _ModType mod() { return _P; }
    static constexpr _ModType mod(uint64_t __a) { return __a % _P; }
    static constexpr _ModType plus(_ModType __a, _ModType __b) {
        if (__a += __b; __a >= _P) __a -= _P;
        return __a;
    }
    static constexpr _ModType minus(_ModType __a, _ModType __b) {
        if (__a += _P - __b; __a >= _P) __a -= _P;
        return __a;
    }
    static constexpr _ModType multiply(uint64_t __a, uint64_t __b) {
        if constexpr (std::is_same<_ModType, uint64_t>::value) return multiply_ld(__a, __b);
        else return multiply_64(__a, __b);
    }
    static constexpr _ModType multiply_64(uint64_t __a, uint64_t __b) { return mod(__a * __b); }
    static constexpr _ModType multiply_128(uint64_t __a, uint64_t __b) { return __uint128_t(__a) * __b % _P; }
    static constexpr _ModType multiply_ld(uint64_t __a, uint64_t __b) {
        if (std::__countl_zero(__a) + std::__countl_zero(__b) >= 64) return multiply_64(__a, __b);
        int64_t res = __a * __b - uint64_t(1.L / _P * __a * __b) * _P;
        if (res < 0) res += _P;
        else if (res >= _P) res -= _P;
        return res;
    }
    static constexpr _ModType pow(uint64_t __a, uint64_t __n) {
        if constexpr (std::is_same<_ModType, uint64_t>::value) return pow_ld(__a, __n);
        else return pow_64(__a, __n);
    }
    static constexpr _ModType pow_64(uint64_t __a, uint64_t __n) {
        _ModType res = 1, b = mod(__a);
        while (__n) {
            if (__n & 1) res = multiply_64(res, b);
            b = multiply_64(b, b);
            __n >>= 1;
        }
        return res;
    }
    static constexpr _ModType pow_128(uint64_t __a, uint64_t __n) {
        _ModType res = 1, b = mod(__a);
        while (__n) {
            if (__n & 1) res = multiply_128(res, b);
            b = multiply_128(b, b);
            __n >>= 1;
        }
        return res;
    }
    static constexpr _ModType pow_ld(uint64_t __a, uint64_t __n) {
        _ModType res = 1, b = mod(__a);
        while (__n) {
            if (__n & 1) res = multiply_ld(res, b);
            b = multiply_ld(b, b);
            __n >>= 1;
        }
        return res;
    }
    template <typename _Tp>
    static constexpr _Tp divide(_Tp __a) { return __a / _P; }
    template <typename _Tp>
    static constexpr std::pair<_Tp, _Tp> divmod(_Tp __a) {
        _Tp quo = __a / _P, rem = __a - quo * _P;
        return {quo, rem};
    }
};
template <uint32_t _P>
using Modular32 = Modular<uint32_t, _P>;
template <uint64_t _P>
using Modular64 = Modular<uint64_t, _P>;
}
namespace OY {
template <typename _ModType, _ModType _P, bool _IsPrime = false>
struct StaticModInt {
    using mint = StaticModInt<_ModType, _P, _IsPrime>;
    _ModType m_val;
    static constexpr _ModType get_primitive_root_prime() {
        _ModType tmp[64] = {};
        int cnt = 0;
        const _ModType phi = _P - 1;
        _ModType m = phi;
        for (_ModType i = 2; i * i <= m; ++i) {
            if (m % i == 0) {
                tmp[cnt++] = i;
                do m /= i;
                while (m % i == 0);
            }
        }
        if (m != 1) tmp[cnt++] = m;
        for (StaticModInt res = 2;; res += 1) {
            bool f = true;
            for (int i = 0; i < cnt && f; ++i) f &= res.pow(phi / tmp[i]) != 1;
            if (f) return _ModType(res);
        }
    }
    static_assert(_P > 1 && _P < 1ull << 63);
    constexpr StaticModInt() : m_val(0) {}
    template <typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value, bool>::type = true>
    constexpr StaticModInt(_Tp __val) : m_val(0) {
        int64_t x = int64_t(__val) % int64_t(mod());
        if (x < 0) x += mod();
        m_val = x;
    }
    template <typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value, bool>::type = true>
    constexpr StaticModInt(_Tp __val) : m_val(__val % mod()) {}
    static constexpr mint raw(_ModType __val) {
        mint res;
        res.m_val = __val;
        return res;
    }
    static constexpr _ModType mod() { return _P; }
    constexpr _ModType val() const { return m_val; }
    constexpr mint pow(uint64_t __n) const { return Modular<_ModType, _P>::pow(m_val, __n); }
    constexpr mint inv() const {
        if constexpr (_IsPrime) return inv_Fermat();
        else return inv_exgcd();
    }
    constexpr mint inv_exgcd() const {
        _ModType x = mod(), y = m_val, m0 = 0, m1 = 1;
        while (y) {
            _ModType z = x / y;
            x -= y * z;
            m0 -= m1 * z;
            std::swap(x, y);
            std::swap(m0, m1);
        }
        if (m0 >= mod()) m0 += mod() / x;
        return raw(m0);
    }
    constexpr mint inv_Fermat() const { return pow(mod() - 2); }
    constexpr mint &operator++() {
        if (++m_val == mod()) m_val = 0;
        return *this;
    }
    constexpr mint &operator--() {
        if (m_val == 0) m_val = mod();
        m_val--;
        return *this;
    }
    constexpr mint operator++(int) {
        mint old(*this);
        ++*this;
        return old;
    }
    constexpr mint operator--(int) {
        mint old(*this);
        --*this;
        return old;
    }
    constexpr mint &operator+=(const mint &__other) {
        m_val = Modular<_ModType, _P>::plus(m_val, __other.m_val);
        return *this;
    }
    constexpr mint &operator-=(const mint &__other) {
        m_val = Modular<_ModType, _P>::minus(m_val, __other.m_val);
            return *this;
    }
    constexpr mint &operator*=(const mint &__other) {
        m_val = Modular<_ModType, _P>::multiply(m_val, __other.m_val);
        return *this;
    }
    constexpr mint &operator/=(const mint &__other) { return *this *= __other.inv(); }
    constexpr mint operator+() const { return *this; }
    constexpr mint operator-() const { return raw(m_val ? mod() - m_val : 0); }
    constexpr bool operator==(const mint &__other) const { return m_val == __other.m_val; }
    constexpr bool operator!=(const mint &__other) const { return m_val != __other.m_val; }
    constexpr bool operator<(const mint &__other) const { return m_val < __other.m_val; }
    constexpr bool operator>(const mint &__other) const { return m_val > __other.m_val; }
    constexpr bool operator<=(const mint &__other) const { return m_val <= __other.m_val; }
    constexpr bool operator>=(const mint &__other) const { return m_val <= __other.m_val; }
    template <typename _Tp>
    constexpr explicit operator _Tp() const { return _Tp(m_val); }
    constexpr friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
    constexpr friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
    constexpr friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
    constexpr friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
    template <typename _Istream>
    friend _Istream &operator>>(_Istream &is, mint &self) { return is >> self.m_val; }
    template <typename _Ostream>
    friend _Ostream &operator<<(_Ostream &os, const mint &self) { return os << self.m_val; }
};
template <uint32_t _P, bool _IsPrime>
using StaticModInt32 = StaticModInt<uint32_t, _P, _IsPrime>;
template <uint64_t _P, bool _IsPrime>
using StaticModInt64 = StaticModInt<uint64_t, _P, _IsPrime>;
}
using mint = OY::StaticModInt32<998244353, true>;
using std::vector;
namespace ntt {
static mint omegas[1 << 23];
inline void get_rev(size_t len, int x) {
    static constexpr mint G = 31;
    if (len == 1 || omegas[len + 1]) return;
    mint* ptr = omegas + len;
    ptr[0] = 1;
    ptr[1ul << x] = G.pow(1ul << (21 - x));
    for (int i = x; i; i--) ptr[1ul << (i - 1)] = ptr[1ul << i] * ptr[1ul << i];
    for (size_t i = 1, iend = 1ul << x; i < iend; i++) ptr[i] = ptr[i & (i - 1)] * ptr[i & ((~i) + 1)];
}
inline void NTT(mint* a, size_t n) {
    mint* ptr = omegas + n;
    for (size_t l = n >> 1; l; l >>= 1) {
        mint *k = a;
        for (mint *g = ptr; k < a + n; k += (l << 1), ++g) for (mint *x = k; x < k + l; x++) {
            mint o = x[l] * *g;
            x[l] = *x - o;
            *x += o;
        }
    }
}
inline void INTT(mint* a, size_t n) {
    mint* ptr = omegas + n;
    for (size_t l = 1; l < n; l <<= 1) {
        mint *k = a;
        for (mint *g = ptr; k < a + n; k += (l << 1), ++g) for (mint *x = k; x < k + l; x++) {
            mint o = x[l];
            x[l] = *g * (*x - o);
            *x += o;
        }
    }
    mint invn = mint(n).inv();
    for (size_t i = 0; i < n; i++) a[i] *= invn;
	std::reverse(a + 1, a + n);
}
static mint buf[1 << 23];
}
using ntt::get_rev;
using ntt::NTT;
using ntt::INTT;
inline vector<mint> operator*(const vector<mint>& a, const vector<mint>& b) {
    using ntt::buf;
    size_t anssiz = a.size() + b.size() - 1;
    vector<mint> c(anssiz);
    size_t len = 1;
    int x = -1;
    while (len < anssiz) len <<= 1, x++;
    get_rev(len, x);
    std::fill_n(std::copy_n(a.begin(), a.size(), buf), len - a.size(), mint(0));
    std::fill_n(std::copy_n(b.begin(), b.size(), buf + len), len - b.size(), mint(0));
    NTT(buf, len);
    NTT(buf + len, len);
    for (size_t i = 0; i < len; i++) buf[i] *= buf[i + len];
    INTT(buf, len);
    std::copy_n(buf, anssiz, c.begin());
    return c;
}
inline vector<mint>& operator*=(vector<mint>& a, const vector<mint>& b) {
    using ntt::buf;
    size_t anssiz = a.size() + b.size() - 1;
    size_t len = 1;
    int x = -1;
    while (len < anssiz) len <<= 1, x++;
    get_rev(len, x);
    a.resize(len);
    std::fill_n(std::copy_n(b.begin(), b.size(), buf), len - b.size(), mint(0));
    NTT(a.data(), len);
    NTT(buf, len);
    for (size_t i = 0; i < len; i++) a[i] *= buf[i];
    INTT(a.data(), len);
    a.resize(anssiz);
    return a;
}
inline vector<mint> operator+(const vector<mint>& a, const vector<mint>& b) {
    vector<mint> c(a);
    c.resize(std::max(a.size(), b.size()));
    for (size_t i = 0, iend = b.size(); i < iend; i++) c[i] += b[i];
    return c;
}
inline vector<mint>& operator+=(vector<mint>& a, const vector<mint>& b) {
    a.resize(std::max(a.size(), b.size()));
    for (size_t i = 0, iend = b.size(); i < iend; i++) a[i] += b[i];
    return a;
}
inline vector<mint> operator-(const vector<mint>& a, const vector<mint>& b) {
    vector<mint> c(a);
    c.resize(std::max(a.size(), b.size()));
    for (size_t i = 0, iend = b.size(); i < iend; i++) c[i] -= b[i];
    return c;
}
inline vector<mint>& operator-=(vector<mint>& a, const vector<mint>& b) {
    a.resize(std::max(a.size(), b.size()));
    for (size_t i = 0, iend = b.size(); i < iend; i++) a[i] -= b[i];
    return a;
}
namespace fac_base {
static constexpr mint inv2 = mint(2).inv();
static vector<mint> fac, invfac, inv;
inline void prepare_fac(size_t n) {
    size_t lastlen = fac.size();
    fac.resize(n + 1);
    invfac.resize(n + 1);
    inv.resize(n + 1);
    if (!lastlen) fac[0] = 1;
    for (size_t i = std::max<size_t>(lastlen, 1ul); i <= n; i++) fac[i] = fac[i - 1] * i;
    invfac[n] = fac[n].inv();
    if (lastlen) {
        for (size_t i = n; i >= lastlen; i--) {
            invfac[i - 1] = invfac[i] * i;
            inv[i] = fac[i - 1] * invfac[i];
        }
    }
    else {
        for (size_t i = n; i; i--) {
            invfac[i - 1] = invfac[i] * i;
            inv[i] = fac[i - 1] * invfac[i];
        }
    }
}
}
using fac_base::prepare_fac;
inline vector<mint> inverse(const vector<mint>& a, size_t l) {
    static constexpr mint two(2);
    vector<mint> b{a[0].inv()}, c;
    int x = 1;
    for (size_t lim = 4; lim < (l << 2); lim <<= 1, x++) {
        c.resize(lim);
        std::copy_n(a.begin(), std::min<size_t>(lim >> 1, a.size()), c.begin());
        b.resize(lim);
        get_rev(lim, x);
        NTT(c.data(), lim);
        NTT(b.data(), lim);
        for (size_t i = 0; i < lim; i++) b[i] *= two - (b[i] * c[i]);
        INTT(b.data(), lim);
        b.resize(lim >> 1);
    }
    b.resize(l);
    return b;
}
inline vector<mint> inverse(const vector<mint>& a) { return inverse(a, a.size()); }
inline vector<mint> operator%(const vector<mint>& a, const vector<mint>& b) {
    size_t n = a.size(), m = b.size();
    vector<mint> F(a), G(b);
    vector<mint> Q(G);
    std::reverse(F.begin(), F.end());
    std::reverse(Q.begin(), Q.end());
    Q.resize(n - m + 1);
    Q = inverse(Q) * F;
    Q.resize(n - m + 1);
    std::reverse(Q.begin(), Q.end());
    std::reverse(F.begin(), F.end());
    Q *= G;
    Q.resize(m - 1);
    Q = F - Q;
    Q.resize(m - 1);
    return Q;
}
inline vector<mint> operator/(const vector<mint>& a, const vector<mint>& b) {
    size_t n = a.size(), m = b.size();
    vector<mint> F(a), G(b);
    vector<mint> Q(G);
    std::reverse(F.begin(), F.end());
    std::reverse(Q.begin(), Q.end());
    Q.resize(n - m + 1);
    Q = inverse(Q) * F;
    Q.resize(n - m + 1);
    std::reverse(Q.begin(), Q.end());
    std::reverse(F.begin(), F.end());
    return Q;
}
inline vector<mint> derivate(const vector<mint>& a) {
    vector<mint> ans(a.size() - 1);
    for (size_t i = 1; i < a.size(); i++) ans[i - 1] = a[i] * i;
    return ans;
}
inline vector<mint> integrate(const vector<mint>& a) {
    vector<mint> ans(a.size() + 1);
    prepare_fac(a.size());
    for (size_t i = 1; i < a.size(); i++) ans[i] = a[i - 1] * fac_base::inv[i];
    return ans;
}
inline vector<mint> log(const vector<mint>& a) {
    vector<mint> tmp(inverse(a));
    tmp *= derivate(a);
    tmp = integrate(tmp);
    return tmp;
}
inline vector<mint> exp(const vector<mint>& a) {
    const size_t n = a.size();
    vector<mint> ans{1}, tmp;
    ans.reserve(n << 2);
    for (size_t lim = 2; lim <= (n << 1); lim <<= 1) {
        ans.resize(lim);
        tmp.resize(lim);
        std::copy_n(ans.begin(), std::min(lim >> 1, a.size()), tmp.begin());
        tmp = log(tmp);
        tmp.resize(lim);
        for (size_t i = 0, iend = std::min<size_t>(lim, a.size()); i < iend; i++) tmp[i] = a[i] - tmp[i];
        for (size_t i = std::min<size_t>(lim, a.size()); i < lim; i++) tmp[i] = -tmp[i];
        tmp[0]++;
        ans *= tmp;
        ans.resize(lim);
    }
    ans.resize(n);
    return ans;
}
namespace cipolla {
static constexpr mint none(-1);
static constexpr unsigned long long mod = mint::mod();
mint legrende(unsigned long long a) { return mint(a).pow((mod - 1) >> 1); }
mint find_nsqr(unsigned long long n) {
    for (unsigned long long i = 0; i < mod; i++) if (legrende(i * i - n) == none) return mint(i);
    return none;
}
mint a, n;
class cp {
    mint _M_real, _M_imag;
public:
    inline cp(const mint& r = mint(), const mint& i = mint()) : _M_real(r), _M_imag(i) {}
    inline cp(const cp& o) : _M_real(o._M_real), _M_imag(o._M_imag) {}
    inline cp& operator=(const cp& o) = default;
    inline cp& operator=(const mint& o) {
        _M_real = o;
        _M_imag = 0;
        return *this;
    }
    inline ~cp() = default;
    inline cp operator+(const cp& o) const { return cp(_M_real + o._M_real, _M_imag + o._M_imag); }
    inline cp operator*(const cp& o) const { return cp(_M_real * o._M_real + _M_imag * o._M_imag * (a * a - n), _M_real * o._M_imag + _M_imag * o._M_real); }
    friend inline cp operator-(const cp& o) { return cp(-o._M_real, -o._M_imag); }
    inline cp operator-(const cp& o) const { return *this + -o; }
    inline cp& operator+=(const cp& o) { return *this = *this + o; }
    inline cp& operator*=(const cp& o) { return *this = *this * o; }
    inline cp& operator-=(const cp& o) { return *this = *this - o; }
    inline mint& real() { return _M_real; }
    inline mint& imag() { return _M_imag; }
    inline const mint& real() const { return _M_real; }
    inline const mint& imag() const { return _M_imag; }
    inline cp conj() const { return cp(_M_real, -_M_imag); }
};
inline cp qpow(const cp& bs, unsigned long long po) {
    cp ans(1, 0), base(bs);
    while (po) {
        if (po & 1) ans *= base;
        base *= base;
        po >>= 1;
    }
    return ans;
}
inline mint sqrt(const mint& nn) {
    n = nn;
    if (n == mint(0)) return mint(0);
    if (legrende(n.val()) != 1) return none;
    a = find_nsqr(n.val());
    mint tmp = qpow(cp(a, 1), (mod + 1) >> 1).real();
    return tmp.val() < (-tmp).val() ? tmp : -tmp;
}
}
namespace sqr {
inline vector<mint> sqr(const vector<mint>& a) {
    using ntt::buf;
    size_t anssiz = a.size() * 2 - 1;
    vector<mint> c(anssiz);
    size_t len = 1;
    int x = -1;
    while (len < anssiz) len <<= 1, x++;
    get_rev(len, x);
    std::fill_n(std::copy_n(a.begin(), a.size(), buf), len - a.size(), mint(0));
    NTT(buf, len);
    for (size_t i = 0; i < len; i++) buf[i] *= buf[i];
    INTT(buf, len);
    std::copy_n(buf, anssiz, c.begin());
    return c;
}
}
vector<mint> sqrt(const vector<mint>& arr) {
    using cipolla::none;
    using fac_base::inv2;
    mint sqrt_of_first = cipolla::sqrt(arr[0]);
    static constexpr mint one(1);
    if (sqrt_of_first == none && arr[0] != one) return vector<mint>();
    if ((sqrt_of_first.val() << 1) >= mint::mod()) sqrt_of_first = -sqrt_of_first;
    vector<mint> ans{sqrt_of_first};
    const size_t n = arr.size();
    for (size_t lim = 2; lim < (n << 2); lim <<= 1) {
        ans = (sqr::sqr(ans) + arr) * inverse(ans);
        ans.resize(lim);
        for (mint& v : ans) v *= inv2;
    }
    ans.resize(arr.size());
    return ans;
}
namespace sin_cos {
static constexpr mint img = 86583718;
static constexpr mint inv2img = (img * 2).inv();
}
vector<mint> sin(const vector<mint>& arr) {
    vector<mint> tmp(arr);
    for (mint& v : tmp) v *= sin_cos::img;
    tmp = exp(tmp);
    vector<mint> ans(inverse(tmp));
    for (size_t i = 0, iend = arr.size(); i < iend; i++) ans[i] = (tmp[i] - ans[i]) * sin_cos::inv2img;
    return ans;
}
vector<mint> cos(const vector<mint>& arr) {
    using fac_base::inv2;
    vector<mint> tmp(arr);
    for (mint& v : tmp) v *= sin_cos::img;
    tmp = exp(tmp);
    vector<mint> ans(inverse(tmp));
    for (size_t i = 0, iend = arr.size(); i < iend; i++) ans[i] = (ans[i] + tmp[i]) * inv2;
    return ans;
}
vector<mint> asin(const vector<mint>& arr) {
    vector<mint> tmp(sqr::sqr(arr));
    for (mint& v : tmp) v = -v;
    tmp[0]++;
    return integrate(derivate(arr) * inverse(sqrt(tmp)));
}
vector<mint> atan(const vector<mint>& arr) {
    vector<mint> tmp(sqr::sqr(arr));
    tmp[0]++;
    return integrate(derivate(arr) * inverse(tmp));
}
vector<mint> pow(const vector<mint>& arr, size_t power) {
    auto it = std::find_if(arr.begin(), arr.end(), [=](const mint& v) { return v.val() != 0; });
    if (!power) {
        vector<mint> ans(arr.size(), mint(0));
        ans[0] = 1;
        return ans;
    }
    if ((it - arr.begin()) * power >= arr.size()) return vector<mint>(arr.size(), mint(0));
    vector<mint> ans(it, arr.end());
    mint tmp = it->inv();
    for (mint& v : ans) v *= tmp;
    ans = log(ans);
    for (mint& v : ans) v *= power;
    ans = exp(ans);
    tmp = it->pow(power);
    for (mint& v : ans) v *= tmp;
    ans.insert(ans.begin(), std::min<size_t>((it - arr.begin()) * power, arr.size()), mint(0));
    return ans;
}
vector<mint> pow(const vector<mint>& arr, size_t power, size_t __power, size_t __flg_power) {
    auto it = std::find_if(arr.begin(), arr.end(), [=](const mint& v) { return v.val() != 0; });
    if ((it - arr.begin()) * __flg_power >= arr.size() || it == arr.end()) return vector<mint>(arr.size(), mint(0));
    vector<mint> ans(it, arr.end());
    mint tmp = it->inv();
    for (mint& v : ans) v *= tmp;
    ans = log(ans);
    for (mint& v : ans) v *= power;
    ans = exp(ans);
    tmp = it->pow(__power);
    for (mint& v : ans) v *= tmp;
    ans.insert(ans.begin(), std::min<size_t>((it - arr.begin()) * power, arr.size()), mint(0));
    return ans;
}
namespace eval_base {
struct SegTree {
    size_t l, r;
    vector<mint> d, dr;
    SegTree *left, *right;
    inline void pushup_d() { d = right->dr * left->d + left->dr * right->d; }
    inline void pushup_dr() { dr = left->dr * right->dr; }
    inline void pushup() {
        pushup_d();
        pushup_dr();
    }
    void build_eval(const vector<mint>& arr) {
        if (l == r) {
            dr.resize(2);
            dr[0] = mint::mod() - arr[l];
            dr[1] = 1;
            d.resize(1);
            d[0] = arr[l];
            return;
        }
        left->build_eval(arr);
        right->build_eval(arr);
        pushup();
    }
    void build_ffp(const vector<mint>& arr) {
        if (l == r) {
            dr.resize(2);
            dr[0] = mint::mod() - l;
            dr[1] = 1;
            d.resize(1);
            d[0] = arr[l];
            return;
        }
        left->build_ffp(arr);
        right->build_ffp(arr);
        pushup();
    }
    void build_poly(const vector<mint>& arr) {
        if (l == r) {
            dr.resize(2);
            dr[0] = mint::mod() - l;
            dr[1] = 1;
            return;
        }
        left->build_poly(arr);
        right->build_poly(arr);
        pushup_dr();
    }
    void build_inter(const vector<mint>& arr) {
        if (l == r) {
            d.resize(1);
            d[0] = arr[l];
            return;
        }
        left->build_inter(arr);
        right->build_inter(arr);
        pushup_d();
    }
    void init_tree() {
        if (l == r) return;
        size_t mid = l + ((r - l) >> 1);
        left = new SegTree(l, mid);
        right = new SegTree(mid + 1, r);
        left->init_tree();
        right->init_tree();
    }
    SegTree(size_t il = 0, size_t ir = 0,
        const vector<mint>& d_ = vector<mint>(),
        const vector<mint>& dr_ = vector<mint>(),
        SegTree *ls = nullptr, SegTree *rs = nullptr)
        : l(il), r(ir), d(d_), dr(dr_), left(ls), right(rs) {}
};
SegTree *root;
vector<mint> ans;
void cdq(SegTree *cur, const vector<mint>& arr) {
    if (cur->l == cur->r) {
        ans[cur->l] = arr[0];
        return;
    }
    eval_base::cdq(cur->left, arr % cur->left->dr);
    eval_base::cdq(cur->right, arr % cur->right->dr);
}
vector<mint> eval(const vector<mint>& arr, const vector<mint>& point_x) {
    const size_t m = point_x.size();
    ans.resize(m);
    root = new SegTree(0, m);
    root->init_tree();
    root->build_eval(point_x);
    eval_base::cdq(root, arr);
    return ans;
}
}
using eval_base::eval;
namespace interpolation {
using eval_base::root;
using eval_base::SegTree;
using eval_base::ans;
vector<mint> tmparr;
void cdq(SegTree *cur, const vector<mint>& arr) {
    if (cur->r - cur->l < 256) {
        for (size_t i = cur->l; i <= cur->r; i++) {
            mint tmp(0);
            const mint x = tmparr[i];
            for (size_t j = arr.size() - 1; ~j; j--) tmp = tmp * x + arr[j];
            ans[i] = tmp;
        }
        return;
    }
    interpolation::cdq(cur->left, arr % cur->left->dr);
    interpolation::cdq(cur->right, arr % cur->right->dr);
}
vector<mint> interpolate(const vector<mint>& point_x, const vector<mint>& point_y) {
    const size_t n = point_x.size();
    ans.resize(n);
    tmparr = point_x;
    root = new SegTree(0, n - 1);
    root->init_tree();
    root->build_eval(point_x);
    interpolation::cdq(root, derivate(root->dr));
    for (size_t i = 0; i < n; i++) ans[i] = point_y[i] / ans[i];
    root->build_inter(ans);
    ans = root->d;
    delete root;
    return ans;
}
}
using interpolation::interpolate;
namespace ffp {
using eval_base::root;
using eval_base::SegTree;
using eval_base::ans;
void cdq(SegTree *cur, const vector<mint>& arr) {
    if (cur->l == cur->r) {
        ans[cur->l] = arr[0];
        return;
    }
    ffp::cdq(cur->left, arr % cur->left->dr);
    ffp::cdq(cur->right, arr % cur->right->dr);
}
vector<mint> poly_to_ffp(const vector<mint>& arr) {
    using fac_base::invfac;
    const size_t n = arr.size();
    prepare_fac(n);
    ans.resize(n);
    vector<mint> tmp(n);
    root = new SegTree(0, n - 1);
    root->init_tree();
    root->build_poly(arr);
    ffp::cdq(root, arr);
    for (size_t i = 0; i < n; i++) {
        tmp[i] = i & 1 ? -invfac[i] : invfac[i];
        ans[i] *= invfac[i];
    }
    return ans * tmp;
}
vector<mint> ffp_to_poly(const vector<mint>& arr) {
    using fac_base::invfac;
    const size_t n = arr.size();
    prepare_fac(n);
    vector<mint> tmp = arr * invfac;
    tmp.resize(n + 1);
    for (size_t i = 0; i <= n; i++) {
        tmp[i] *= invfac[n - i];
        if ((n - i) & 1) tmp[i] = -tmp[i];
    }
    root = new SegTree(0, n);
    root->init_tree();
    root->build_ffp(tmp);
    tmp = root->d;
    delete root;
    return tmp;
}
}
using ffp::poly_to_ffp;
using ffp::ffp_to_poly;
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
    vector<mint> pa(a, a + n + 1), pb(b, b + m + 1);
    pa *= pb;
    memcpy(c, pa.data(), pa.size() * sizeof(mint));
}

评测结果