Language: C++

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#ifndef MAJK_LIB
#define MAJK_LIB

#include <vector>
#include <stack>
#include <iostream>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <fstream>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <string>
#include <sstream>
#include <queue>
#include <bitset>
using namespace std;

#define x first
#define y second
constexpr int MOD = 1000000007;

typedef std::pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
auto fraclt = [](const pii&a,const pii&b) { return (ll)a.x * b.y < (ll)b.x * a.y; };
struct cmpfrac { bool operator()(const pii&a,const pii&b)const { return (ll)a.x * b.y < (ll)b.x * a.y; }};
template <typename T> bool in(T a, T b, T c) { return a <= b && b < c; }
int logceil(ll x) {int b=0;while(x){x>>=1;++b;}return b;}

namespace std {
    template<typename T,typename U>struct hash<pair<T,U>>{hash<T>t;hash<U>u;size_t operator()(const pair<T,U>&p)const{return t(p.x)^(u(p.y)<<7);}};
}
template<typename T,typename F>T bsh(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){l=m+1;r=m;}else{h=m-1;}}return r;}
template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;}
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }

template<typename T>class vector2:public vector<vector<T>>{public:vector2(){} vector2(size_t a,size_t b,T t=T()):vector<vector<T>>(a,vector<T>(b,t)){}};
template<typename T>class vector3:public vector<vector<vector<T>>>{public:vector3(){} vector3(size_t a,size_t b,size_t c,T t=T()):vector<vector<vector<T>>>(a,vector<vector<T>>(b,vector<T>(c,t))){}};
template <typename T> struct bounded_priority_queue {
	inline bounded_priority_queue(ui X) : A(X), B(0) {}
	inline void push(ui L, T V) { B = max(B, L); A[L].push(V); }
	inline const T &top() const { return A[B].front(); }
	inline void pop() { A[B].pop(); while (B > 0 && A[B].empty()) --B; }
	inline bool empty() const { return A[B].empty(); }
	inline void clear() { B = 0; for (auto &a: A) a = queue<T>(); }
private:
	vector<queue<T>> A; ui B;
};


#endif
#ifndef MOD_H
#define MOD_H




struct UnionFind {
	UnionFind(size_t N) : P(N, -1), comp(N) {}
	int find(int x) { while (P[x]>=0){x = P[x];}return x; }
	bool united(int x, int y) { return find(x) == find(y); }
	bool unite(int x, int y) { x=find(x);y=find(y);if(x==y){return false;}--comp;if(P[x]>P[y]){swap(x,y);}P[x]+=P[y];P[y]=x;return true;}
	vector<int> P;
	size_t comp;
};

/** Multiply two 64-bit unsigned integers to get a 128-bit unsigned integer (as a pair of ull) */
pair<ull,ull> mulull(ull a, ull b) {
#ifdef __SIZEOF_INT128__
	__int128 result = (__int128) a * (__int128) b;
	return {(ull) (result >> 64), (ull) result};
#else
	ull c = (ui)a, d = a>>32, e = (ui)b, f = b>>32, g = d*f, h = d*e, i = f*c, j = c*e, k = (j>>32)+(ui)h+(ui)i, l = g+(h>>32)+(i>>32)+(k>>32);
	return {l, ((h+i) << 32) + j};
#endif
}

bool fractionGreaterOrEqual(ll a, ll b, ll c, ll d) {
	if (b < 0) { b = -b; a = -a; }
	if (d < 0) { d = -d; c = -c; }
	return a < 0 && c < 0 ? mulull(-a, d) <= mulull(-c, b) : (a >= 0) && (c < 0 || mulull(a, d) >= mulull(c, b));
}

bool fractionGreaterOrEqual(double a, double b, double c, double d) {
	return a/b >= c/d;
}

// this is based on modulus, but it's 2-3 times slower than the former
//bool fractionGreaterOrEqual(ll a, ll b, ll c, ll d) {
//	if (a<0 && c<0) return greaterOrEqual(-c,d,-a,b);
//	if (a<0) return false;
//	if (c<0) return true;
//	if (b==0) return true;
//	if (d==0) return false;
//	ll ab = a/b, cd = c/d;
//	if (ab > cd) return true;
//	if (ab < cd) return false;
//	return !greaterOrEqual(b, a%b, d, c%d);
//}


/** Computing lower and upper envelope. Useful for "convex hull trick". */
namespace Envelope {
	template<typename T>
	struct Line {
		T m, b;
		mutable function<const Line<T> *()> succ;

		bool operator<(const Line &rhs) const {
			if (rhs.b != numeric_limits<T>::min()) return m < rhs.m;
			const Line *s = succ();
			if (!s) return 0;
			return b - s->b < (s->m - m) * rhs.m;
		}
	};

	template<typename T>
	struct Upper : public multiset<Envelope::Line<T>> {
		using parent = multiset<Line<T>>;

		bool bad(typename parent::iterator y) {
			auto z = next(y);
			if (y == parent::begin()) {
				return z != parent::end() && y->m == z->m && y->b <= z->b;
			} else {
				auto x = prev(y);
				if (z == parent::end()) {
					return y->m == x->m && y->b <= x->b;
				} else {
					return fractionGreaterOrEqual(x->b - y->b, y->m - x->m, y->b - z->b, z->m - y->m);
				}
			}
		}

		void insert_line(T m, T b) {
			auto y = parent::insert({m, b});
			y->succ = [=] { return next(y) == parent::end() ? 0 : &*next(y); };
			if (bad(y)) { parent::erase(y); return; }
			while (next(y) != parent::end() && bad(next(y))) parent::erase(next(y));
			while (y != parent::begin() && bad(prev(y))) parent::erase(prev(y));
		}

		T operator[](T x) const {
			auto l = parent::lower_bound({x, numeric_limits<T>::min()});
			return l == parent::end() ? numeric_limits<T>::min() : l->m * x + l->b;
		}
	};

	template<typename T>
	struct Lower : public Upper<T> {
		void insert_line(T m, T b) { Upper<T>::insert_line(-m, -b); }
		T operator[](T x) const { return -Upper<T>::operator[](x); }
	};
}
#include <array>

template <unsigned int N> class Field {
    typedef unsigned int ui;
    typedef unsigned long long ull;
	inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;}
	/*extended GCD(slow):ll t=0,nt=1,r=N,nr=a;while(nr){ll q=r/nr;t-=q*nt;swap(t,nt);r-=q*nr;swap(r,nr);}assert(r<=1);return(t<0)?t+N:t;*/
	inline ui inv(ui a){return pow(a,N-2);}
public:
    inline Field(int x = 0) : v(x) {}
	inline Field<N> pow(int p){return (*this)^p; }
	inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};}
    inline Field<N>&operator+=(const Field<N>&o) {if ((ll)v+o.v >= N) v = (ll)v+o.v-N; else v = v+o.v; return *this; }
    inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v = N-o.v+v; else v=v-o.v; return *this; }
    inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
    inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); }
    inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}
    inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}
    inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
    inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}
    inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};
    inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }
    inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }
    inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }
    inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }
    inline bool operator==(const Field<N>&o) const { return o.v==v; }
	inline bool operator!=(const Field<N>&o) const { return o.v!=v; }
	inline explicit operator ui() const { return v; }
	inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;}
	inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;}
private: ui v;
};
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}
template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;}


typedef Field<1000000007> FieldMod;

struct Ring {
	static int div(int p, int q, int N) {
		ll t=0,nt=1,r=N,nr=q;
		while(nr){ ll q=r/nr;t-=q*nt;r-=q*nr;swap(t,nt);swap(r,nr); }
		t=(t<0)?t+N:t;
		r=(r<0)?r+N:r;
		if (gcd(p,N)%r) { return 0; }
		return (int)(((ll)t*(ll)p/r)%N);
	}
};
#endif





template <ui P> struct Group {};
template <> struct Group<4194304001u> { constexpr static ui bits = 25, root = 199, rootInverse = 758768563u; };
template <> struct Group<998244353u> { constexpr static ui bits = 23, root = 31, rootInverse = 128805723; };
template <> struct Group<104857601u> { constexpr static ui bits = 22, root = 21, rootInverse = 49932191; };
template <> struct Group<924844033u> { constexpr static ui bits = 21, root = 3597, rootInverse = 508059997; };

template <ui Prime> class FFT {
public:
	typedef Field<Prime> F;

	FFT() {
		OMEGA[Group<Prime>::bits] = Group<Prime>::root;
		OMEGA_INV[Group<Prime>::bits] = Group<Prime>::rootInverse;
		for (size_t i = Group<Prime>::bits; i > 0; --i) {
			OMEGA[i-1] = ui((ull(OMEGA[i])*ull(OMEGA[i]))%Prime);
			OMEGA_INV[i-1] = ui((ull(OMEGA_INV[i])*ull(OMEGA_INV[i]))%Prime);

			// cerr << OMEGA[i-1] << ' ' << OMEGA_INV[i-1] << endl;
		}
	}

	void fft(std::vector<F> &V, bool inverse = false) {
		int P = 1;
		while ((1u << P) < V.size()) ++P;
		V.resize(1u << P);
		fft(V, P, inverse);
	}

	void fft(std::vector<F> &V, const int P, bool inverse = false) {
		if (P == 0) return;
		if (P > Group<Prime>::bits) throw std::runtime_error("Number of bits in FFT too large");
		if (V.size() != (1 << P)) throw std::runtime_error("Vector has wrong size");
		for (int i = 1, j = 0; i < (1 << P); ++i) {
			int bit = (1 << (P - 1));
			for (; j >= bit; bit >>= 1) j -= bit;
			j += bit;
			if (i < j) std::swap(V[i], V[j]);
		}

		for (int B = 1; B <= P; ++B) {
			F omega = inverse ? OMEGA_INV[B] : OMEGA[B];
			for (int i = 0; i < (1 << P); i += (1 << B)) {
				F x = 1;
				for (int j = 0; j < (1 << (B - 1)); j++) {
					F u = V[i + j], v = V[i + j + (1 << (B - 1))] * x;
					V[i + j] = u + v;
					V[i + j + (1 << (B - 1))] = u - v;
					x *= omega;
				}
			}
		}

		if (inverse) {
			F q = 1 / F(1 << P);
			for (F &v:V) v *= q;
		}
	}

private:
	std::array<ui, Group<Prime>::bits+1> OMEGA, OMEGA_INV;
};

#ifndef MAJK_CRT
#define MAJK_CRT


#ifndef MAJK_BIGINT
#define MAJK_BIGINT

#include <math.h>
#include <stdint.h>
#include <limits.h>




class Num {
public:
    typedef uint64_t word;

    std::vector<word> words;
    bool neg;

    static word word_mask(){
        return (word)-1;
    }

    static size_t word_bits(){
        return sizeof(word)*CHAR_BIT;
    }

    static word word_half_mask(){
        return word_mask() >> word_bits()/2;
    }

    static word char_to_word(char c){
        switch (c){
            case '0': return 0;
            case '1': return 1;
            case '2': return 2;
            case '3': return 3;
            case '4': return 4;
            case '5': return 5;
            case '6': return 6;
            case '7': return 7;
            case '8': return 8;
            case '9': return 9;
            case 'a': case 'A': return 10;
            case 'b': case 'B': return 11;
            case 'c': case 'C': return 12;
            case 'd': case 'D': return 13;
            case 'e': case 'E': return 14;
            case 'f': case 'F': return 15;
            case 'g': case 'G': return 16;
            case 'h': case 'H': return 17;
            case 'i': case 'I': return 18;
            case 'j': case 'J': return 19;
            case 'k': case 'K': return 20;
            case 'l': case 'L': return 21;
            case 'm': case 'M': return 22;
            case 'n': case 'N': return 23;
            case 'o': case 'O': return 24;
            case 'p': case 'P': return 25;
            case 'q': case 'Q': return 26;
            case 'r': case 'R': return 27;
            case 's': case 'S': return 28;
            case 't': case 'T': return 29;
            case 'u': case 'U': return 30;
            case 'v': case 'V': return 31;
            case 'w': case 'W': return 32;
            case 'x': case 'X': return 33;
            case 'y': case 'Y': return 34;
            case 'z': case 'Z': return 35;
            default: return word_mask();
        }
    }

    static word word_gcd(word a, word b){
        while (1){
            if (a == 0) return b;
            b %= a;
            if (b == 0) return a;
            a %= b;
        }
    }

    Num(): neg(false){}

    Num(size_t n, word w, bool neg = false): words(n, w), neg(neg){}

    Num(const word *a, const word *b, bool neg = false) : words(a, b), neg(neg){}

    Num(const Num &a){
        words = a.words;
        neg = a.neg;
    }

    Num& operator= (const Num &a){
        words = a.words;
        neg = a.neg;
        return *this;
    }

    Num(long long i): neg(i < 0) {
        for (unsigned u = std::abs(i); u;){
            push_back(u);
            for (size_t j = 0; j < word_bits(); j++) u >>= 1;
        }
    }

    Num(std::string s, word base = 10): neg(false){
        if (s[0] == '-'){
            neg = true;
        }
        for (int i = neg; i < s.size(); i++){
            mul_word(base);
            word b = char_to_word(s[i]);
            if (b >= base) break;
            add_word(b);
        }
    }

    void resize(size_t n){
        words.resize(n);
    }

    void pop_back(){
        words.pop_back();
    }

    void push_back(word b){
        words.push_back(b);
    }

    word& back(){
        return words.back();
    }

    const word& back() const {
        return words.back();
    }

    size_t size() const {
        return words.size();
    }

    word& operator [] (size_t i){
        return words[i];
    }

    const word& operator [] (size_t i) const {
        return words[i];
    }

    Num& set_neg(bool neg){
        this->neg = neg;
        return *this;
    }

    Num& truncate(){
        while (size() > 0 && words.back() == 0) pop_back();
        return *this;
    }

    size_t bitlength() const {
        if (size() == 0) return 0;
        size_t last = size() - 1;
        size_t result = word_bitlength((*this)[last]) + last*word_bits();
        return result;
    }

    size_t count_trailing_zeros() const {
        for (size_t i = 0; i < size(); i++){
            word w = (*this)[i];
            if (w) return word_count_trailing_zeros(w) + i*word_bits();
        }
        return 0;
    }

    static int cmp_abs(const Num &a, const Num &b){
        size_t na = a.size(), nb = b.size();
        if (na != nb){
            return na < nb ? -1 : +1;
        }
        for (size_t i = na; i --> 0;){
            word wa = a[i], wb = b[i];
            if (wa != wb){
                return wa < wb ? -1 : +1;
            }
        }
        return 0;
    }

    static int cmp(const Num &a, const Num &b){
        if (a.size() == 0 && b.size() == 0) return 0;
        if (!a.neg && !b.neg) return +cmp_abs(a, b);
        if ( a.neg &&  b.neg) return -cmp_abs(a, b);
        return a.neg && !b.neg ? -1 : +1;
    }

    static size_t word_bitlength(word a){
        for (int i = word_bits() - 1; i >= 0; i--) if ((a >> i) & 1) return i+1;
        return 0;
    }

    static size_t word_count_trailing_zeros(word a){
        for (int i = 0; i < (int)word_bits(); i++) if ((a >> i) & 1) return i;
        return word_bits();
    }

    static word add_carry(word *a, word b){
        return (*a += b) < b;
    }

    static word sub_carry(word *a, word b){
        word tmp = *a;
        return (*a = tmp - b) > tmp;
    }

    static word word_mul_hi(word a, word b){
        size_t n = word_bits()/2;
        word a_hi = a >> n;
        word a_lo = a & word_half_mask();
        word b_hi = b >> n;
        word b_lo = b & word_half_mask();
        word tmp = ((a_lo*b_lo) >> n) + a_hi*b_lo;
        tmp = (tmp >> n) + ((a_lo*b_hi + (tmp & word_half_mask())) >> n);
        return tmp + a_hi*b_hi;
    }

    static Num& add_unsigned_overwrite(Num &a, const Num &b){
        size_t i, na = a.size(), nb = b.size(), n = std::max(na, nb);
        a.resize(n);
        word carry = 0;
        for (i = 0; i < nb; i++){
            carry  = add_carry(&a[i], carry);
            carry += add_carry(&a[i], b[i]);
        }
        for (; i < n && carry; i++) carry = add_carry(&a[i], carry);
        if (carry) a.push_back(carry);
        return a.truncate();
    }

    static Num& sub_unsigned_overwrite(Num &a, const Num &b){
        //assert(cmp_abs(a, b) >= 0);
        size_t i, na = a.size(), nb = b.size();
        word carry = 0;
        for (i = 0; i < nb; i++){
            carry  = sub_carry(&a[i], carry);
            carry += sub_carry(&a[i], b[i]);
        }
        for (; i < na && carry; i++) carry = sub_carry(&a[i], carry);
        //assert(!carry);
        return a.truncate();
    }

    static Num mul_long(const Num &a, const Num &b){
        size_t na = a.size(), nb = b.size(), nc = na + nb + 1;
        Num c(nc, 0, a.neg ^ b.neg), carries(nc, 0);
        for (size_t ia = 0; ia < na; ia++){
            for (size_t ib = 0; ib < nb; ib++){
                size_t i = ia + ib, j = i + 1;
                // WARNING: Might overflow if word size is chosen too small
                carries[i + 1] += add_carry(&c[i], a[ia] * b[ib]);
                carries[j + 1] += add_carry(&c[j], word_mul_hi(a[ia], b[ib]));
            }
        }
        return add_unsigned_overwrite(c, carries).truncate();
    }

    static Num mul_karatsuba(const Num &a, const Num &b){
        size_t na = a.size(), nb = b.size(), n = std::max(na, nb), m2 = n/2 + (n & 1);
        Num a_parts[2], b_parts[2];
        split(a, a_parts, 2, m2);
        split(b, b_parts, 2, m2);
        m2 *= word_bits();
        Num z0 = a_parts[0] * b_parts[0];
        Num z1 = (a_parts[0] + a_parts[1]) * (b_parts[0] + b_parts[1]);
        Num z2 = a_parts[1] * b_parts[1];
        Num result = z2;
        result <<= m2;
        result += z1 - z2 - z0;
        result <<= m2;
        result += z0;
        return result;
    }

    static Num mul(const Num &a, const Num &b){
        size_t karatsuba_threshold = 20;
        if (a.size() > karatsuba_threshold && b.size() > karatsuba_threshold){
            return mul_karatsuba(a, b);
        }
        return mul_long(a, b);
    }

    static Num add_signed(const Num &a, bool a_neg, const Num &b, bool b_neg){
        if (a_neg == b_neg) return add_unsigned(a, b).set_neg(a_neg);
        if (cmp_abs(a, b) >= 0) return sub_unsigned(a, b).set_neg(a_neg);
        return sub_unsigned(b, a).set_neg(b_neg);
    }

    Num& operator >>= (size_t n_bits){
        if (n_bits == 0) return *this;
        size_t n_words = n_bits / word_bits();
        if (n_words >= size()){
            resize(0);
            return *this;
        }
        n_bits %= word_bits();
        if (n_bits == 0){
            for (size_t i = 0; i < size() - n_words; i++){
                (*this)[i] = (*this)[i + n_words];
            }
        }else{
            word hi, lo = (*this)[n_words];
            for (size_t i = 0; i < size() - n_words - 1; i++){
                hi = (*this)[i + n_words + 1];
                (*this)[i] = (hi << (word_bits() - n_bits)) | (lo >> n_bits);
                lo = hi;
            }
            (*this)[size() - n_words - 1] = lo >> n_bits;
        }
        resize(size() - n_words);
        return truncate();
    }

    Num& operator <<= (size_t n_bits){
        if (n_bits == 0) return *this;
        size_t n_words = n_bits / word_bits();
        n_bits %= word_bits();
        size_t old_size = size();
        size_t n = old_size + n_words + (n_bits != 0);
        resize(n);
        if (n_bits == 0){
            for (size_t i = n; i --> n_words;){
                (*this)[i] = (*this)[i - n_words];
            }
        }else{
            word lo, hi = 0;
            for (size_t i = n - 1; i > n_words; i--){
                lo = (*this)[i - n_words - 1];
                (*this)[i] = (hi << n_bits) | (lo >> (word_bits() - n_bits));
                hi = lo;
            }
            (*this)[n_words] = hi << n_bits;
        }
        for (size_t i = 0; i < n_words; i++) (*this)[i] = 0;
        return truncate();
    }

    static void div_mod(const Num &numerator, Num denominator, Num &quotient, Num &remainder){
        quotient = 0;
        remainder = numerator;
        if (cmp_abs(remainder, denominator) >= 0){
            int n = numerator.bitlength() - denominator.bitlength();
            denominator <<= n;
            for (; n >= 0; n--){
                if (cmp_abs(remainder, denominator) >= 0){
                    sub_unsigned_overwrite(remainder, denominator);
                    quotient.set_bit(n);
                }
                denominator >>= 1;
            }
        }
        quotient.set_neg(numerator.neg ^ denominator.neg);
        remainder.set_neg(numerator.neg);
    }

    static void div_mod_half_word(const Num &numerator, word denominator, Num &quotient, word &remainder){
        remainder = 0;
        Num dst(numerator.size(), 0);

        for (size_t i = numerator.size(); i --> 0;){
            word dst_word = 0;
            word src_word = numerator[i];
            word parts[2];
            parts[0] = src_word >> word_bits()/2;
            parts[1] = src_word & word_half_mask();

            for (size_t j = 0; j < 2; j++){
                remainder <<= word_bits()/2;
                remainder |= parts[j];

                word div_word = remainder / denominator;
                word mod_word = remainder % denominator;
                remainder = mod_word;

                dst_word <<= word_bits()/2;
                dst_word |= div_word;
            }

            dst[i] = dst_word;
        }

        quotient = dst.truncate().set_neg(numerator.neg);
    }

    static void split(const Num &a, Num *parts, size_t n_parts, size_t n){
        size_t i = 0;
        for (size_t k = 0; k < n_parts; k++){
            Num &part = parts[k];
            part.resize(n);
            for (size_t j = 0; j < n && i < a.size(); j++) part[j] = a[i++];
            part = part.truncate();
        }
    }

    static Num div(const Num &numerator, const Num& denominator){
        Num quotient, remainder;
        div_mod(numerator, denominator, quotient, remainder);
        return quotient;
    }

    static Num mod(const Num &numerator, const Num& denominator){
        Num quotient, remainder;
        div_mod(numerator, denominator, quotient, remainder);
        return remainder;
    }

    static Num add_unsigned(const Num &a, const Num &b){
        Num result(a);
        return add_unsigned_overwrite(result, b);
    }

    static Num sub_unsigned(const Num &a, const Num &b){
        Num result(a);
        return sub_unsigned_overwrite(result, b);
    }

    static Num add(const Num &a, const Num &b){
        Num result = add_signed(a, a.neg, b, b.neg);
        return result;
    }

    static Num sub(const Num &a, const Num &b){
        Num result = add_signed(a, a.neg, b, !b.neg);
        return result;
    }

    static Num gcd(const Num &a0, const Num &b0){

        if (a0.size() == 1 && b0.size() == 1){
            return Num(1, word_gcd(a0[0], b0[0]));
        }

        Num a(a0), b(b0);
        a.neg = b.neg = false;

        if (a.size() == 0) return b0;
        if (b.size() == 0) return a0;

        size_t n = std::min(a.count_trailing_zeros(), b.count_trailing_zeros());

        a >>= n;
        b >>= n;

        do {
            b >>= b.count_trailing_zeros();
            if (cmp_abs(a, b) > 0) a.words.swap(b.words);
            sub_unsigned_overwrite(b, a);
        } while (b.size() > 0);

        a <<= n;

        return a;
    }

    typedef void (*random_func)(uint8_t *bytes, size_t n_bytes);

    static Num random_bits(size_t n_bits, random_func func){
        if (n_bits == 0) return 0;
        size_t partial_bits = n_bits % word_bits();
        size_t n_words = n_bits / word_bits() + (partial_bits > 0);
        size_t n_bytes = n_words*sizeof(word);
        Num result(n_words, 0);
        uint8_t *bytes = (uint8_t*)&result[0];
        func(bytes, n_bytes);
        if (partial_bits){
            size_t too_many_bits = word_bits() - partial_bits;
            result.back() >>= too_many_bits;
        }
        return result;
    }

    static Num random_inclusive(const Num &inclusive, random_func func){
        size_t n_bits = inclusive.bitlength();
        while (true){
            Num result = random_bits(n_bits, func);
            if (result <= inclusive) return result;
        }
    }

    static Num random_exclusive(const Num &exclusive, random_func func){
        size_t n_bits = exclusive.bitlength();
        while (true){
            Num result = random_bits(n_bits, func);
            if (result < exclusive) return result;
        }
    }

    static Num random_second_exclusive(const Num &inclusive_min_val, const Num &exclusive_max_val, random_func func){
        return inclusive_min_val + random_exclusive(exclusive_max_val - inclusive_min_val, func);
    }

    static Num random_both_inclusive(const Num &inclusive_min_val, const Num &inclusive_max_val, random_func func){
        return inclusive_min_val + random_inclusive(inclusive_max_val - inclusive_min_val, func);
    }

    Num& set_bit(size_t i){
        size_t i_word = i / word_bits();
        size_t i_bit =  i % word_bits();
        if (size() <= i_word) resize(i_word + 1);
        (*this)[i_word] |= ((word)1) << i_bit;
        return *this;
    }

    word get_bit(size_t i) const {
        size_t i_word = i / word_bits();
        size_t i_bit =  i % word_bits();
        if (i_word >= size()) return 0;
        return ((*this)[i_word] >> i_bit) & 1;
    }

    void clr_bit(size_t i){
        size_t i_word = i / word_bits();
        size_t i_bit =  i % word_bits();
        if (i_word >= size()) return;
        word mask = 1;
        mask <<= i_bit;
        (*this)[i_word] &= ~mask;
    }

    Num& mul_word(word b){
        word carry = 0;
        for (size_t i = 0; i < size(); i++){
            word a = (*this)[i];
            word tmp = a * b;
            carry = add_carry(&tmp, carry);
            carry += word_mul_hi(a, b);
            (*this)[i] = tmp;
        }
        if (carry) push_back(carry);
        return truncate();
    }

    Num& add_word(word carry, size_t i0 = 0){
        if (i0 >= size()) resize(i0 + 1);
        for (size_t i = i0; i < size() && carry; i++){
            carry = add_carry(&(*this)[i], carry);
        }
        if (carry) push_back(carry);
        return truncate();
    }

    void print(std::ostream&os, word base = 10, const char *alphabet = "0123456789abcdefghijklmnopqrstuvwxyz") const {
        if (size() == 0){
            os << '0';
        }else{
            vector<char> text;
            Num tmp(*this);
            while (tmp.size() > 0){
                word remainder;
                div_mod_half_word(tmp, base, tmp, remainder);
                text.push_back(alphabet[remainder]);
            }
            if (neg) os << '-';
            for (int i = text.size()-1; i >= 0; --i) os << text[i];
        }
    }

    long long to_longlong() const {
        if (size() == 0) return 0;
        word d = (*this)[0];
        return neg ? -d : d;
    }

    double to_double() const {
        if (size() == 0) return 0.0;
        double d = 0.0, base = ::pow(2.0, word_bits());
        for (size_t i = size(); i --> 0;) d = d * base + (*this)[i];
        return neg ? -d : d;
    }

    Num pow(size_t exponent) const {
        Num result(1), p(*this);
        for (; exponent; exponent >>= 1){
            if (exponent & 1){
                result = result * p;
                exponent--;
            }
            p = p*p;
        }
        return result;
    }

    Num mod_pow(Num exponent, const Num &modulus) const {
        Num result(1), base = (*this) % modulus;
        for (; exponent.size() > 0; exponent >>= 1){
            if (exponent.get_bit(0)){
                result = (result * base) % modulus;
            }
            base = (base * base) % modulus;
        }
        return result;
    }

    Num sqrt() const {
        Num n = *this;
        int bit = bitlength();
        if (bit & 1) bit ^= 1;
        Num result = 0;
        for (; bit >= 0; bit -= 2){
            Num tmp = result;
            tmp.set_bit(bit);
            if (n >= tmp){
                n -= tmp;
                result.set_bit(bit + 1);
            }
            result >>= 1;
        }
        return result;
    }

    Num& operator ++(){
        add_word(1);
        return *this;
    }

    Num& operator += (const Num &b){ return *this = add(*this, b); }
    Num& operator -= (const Num &b){ return *this = sub(*this, b); }
    Num& operator *= (const Num &b){ return *this = mul(*this, b); }
    Num& operator /= (const Num &b){ return *this = div(*this, b); }
    Num& operator %= (const Num &b){ return *this = mod(*this, b); }

    bool operator == (const Num &b) const { return cmp(*this, b) == 0; }
    bool operator != (const Num &b) const { return cmp(*this, b) != 0; }
    bool operator <= (const Num &b) const { return cmp(*this, b) <= 0; }
    bool operator >= (const Num &b) const { return cmp(*this, b) >= 0; }
    bool operator <  (const Num &b) const { return cmp(*this, b) <  0; }
    bool operator >  (const Num &b) const { return cmp(*this, b) >  0; }

    Num operator + (const Num &b) const { return add(*this, b); }
    Num operator - (const Num &b) const { return sub(*this, b); }
    Num operator * (const Num &b) const { return mul(*this, b); }
    Num operator / (const Num &b) const { return div(*this, b); }
    Num operator % (const Num &b) const { return mod(*this, b); }
    Num operator - (            ) const { return Num(*this).set_neg(!neg); }

    Num operator >> (size_t n_bits) const { return Num(*this) >>= n_bits; }
    Num operator << (size_t n_bits) const { return Num(*this) <<= n_bits; }
};

#endif


template<ui N,ui M> class Chinese {
public:
    Chinese(const std::array<ui,N> &p) : P(1), p(p) {
        for(int i=0;i<N;++i)P*=p[i];
        for(int i=0;i<N;++i){ F[i]=P/p[i]; }
        for(int i=0;i<N;++i) { T[i]=Ring::div(1, (F[i]%p[i]).to_longlong(), p[i]);}
    }

    ui operator()(const std::array<ui,N> &R) {
        Num X = 0;
        for (int i=0;i<N;++i) X += F[i] * ((ull(R[i])*T[i])%p[i]);
        X %= P;
        X %= M;
        return X.to_longlong();
    }
private:
    Num P;
    std::array<Num,N> F;
    std::array<ui,N> T,p;
};

#endif //MAJK_CRT_H

#ifndef MAJK_RANDOM_H
#define MAJK_RANDOM_H

#include <random>
#include <chrono>
seed_seq seed{(ll)std::random_device{}(), std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count(),(ll)std::hash<std::string>()({
"kjsdfksjdfklsdjfklsdjfkljshdfklsjhfklsdjfhgklsdjfhgkldsfjhgklsjfnvkdjfnvkjsdfvkljsdfnvkjsdnfvlkjnfjrhiuerht34yiuerieurhfieurhgosidfjsodigisodurghsoidufhskdjfghiosdfughiosdufghiosdufghisdfguhskdjvnlskxjcvnsdiufyg9q48yriwuehfiosudfgy87e4hrioeurgiosdrgoisrhgisdurhgoisdruhgsiordughsdrioguhsdrgoi8syrgiuos4hgoisuehgosr8hgsodruihgsodifughlkzjxfxkjcvnblkjdrhgoie4ytijfgklsjdfg"
})};
std::mt19937 rng{seed};
using random_int = std::uniform_int_distribution<int>;
using random_ll = std::uniform_int_distribution<ll>;

#endif //MAJK_RANDOM_H


typedef Field<998244353> TF;
class F {
public:
    FFT<998244353u> Z;
    vector<TF> All, Conv1, Conv2, Ans;

    void perform(int pos, int size) {
        if (size == 1) return;

        perform(pos, size/2);

        vector<TF> Cur(size, 0);
        vector<TF> Mul(size, 0);
        for (int i = 0; i < size/2; ++i) Cur[i] = Ans[i+pos];
        for (int i = 0; i < size; ++i) Mul[i] = Conv1[i];
        Z.fft(Cur);
        Z.fft(Mul);
        for (int i = 0; i < size; ++i) Cur[i] *= Mul[i];
        Z.fft(Cur, true);
        for (int i = 0; i < size/2; ++i) Ans[pos+size/2+i] += Cur[i+size/2-1];

        perform(pos+size/2, size/2);
    }


    void solve(istream& cin, ostream& cout) {
        int N, M; cin >> N >> M;

        M = 1 << logceil(N+1);

        auto F = TF::fact(2*M);
        auto I = TF::invfact(2*M);

        All.clear(); Conv2.clear();
        All.resize(2*M); Conv1.resize(M); Conv2.resize(2*M);
        for (int i = 0; i < M; ++i) {
            All[i] = F[2*i] * I[i] * I[i];
            Conv1[i] = i>0 ? All[i] - F[2*i] * I[i+1] * I[i-1] : 1;
            Conv2[i] = Conv1[i] * (2*i+3);
            Conv1[i] *= 2;
        }

        TF scale = All[N];

        // Ans[i] = sum Conv2[j] * All[i-1-j]
        Z.fft(All);
        Z.fft(Conv2);
        for (int i = 0; i < 2*M; ++i) Conv2[i] *= All[i];
        Z.fft(Conv2, true);
        Ans = vector<TF>(2*M, 0);
        for (int i = 1; i < M; ++i) {
            Ans[i] = Conv2[i - 1];
        }
//
//        for (int i = 1; i < M; ++i) {
//            for (int j = 0; j < i; ++j) {
//                Ans[i] += Conv1[j] * Ans[i-1-j];
//            }
//        }


        perform(0, M);

        cout << Ans[N]/scale << endl;
//
//
//        vector2<TF> D(N+1, M+1, 0);
//        for (int i = 0; i <= N; ++i) {
//            D[i][0] = i;
//        }
//        for (int i = 0; i <= M; ++i) {
//            D[0][i] = i;
//        }
//
//        for (int i = 1; i <= N; ++i) {
//            for (int j = 1; j <= M; ++j) {
//                D[i][j] = (D[i][j-1]*j + D[i-1][j]*i + max(i,j))/(i+j);
//            }
//        }
//        cout << D[N][M] << endl;
    }
};


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	F solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}


Compiler output:
a.cc:975:3: error: no matching function for call to 'std::seed_seq::seed_seq(<brace-enclosed initializer list>)'
  975 | })};
      |   ^
In file included from /usr/include/c++/14/random:48,
                 from a.cc:971:
/usr/include/c++/14/bits/random.h:6375:7: note: candidate: 'template<class _InputIterator> std::seed_seq::seed_seq(_InputIterator, _InputIterator)'
 6375 |       seed_seq(_InputIterator __begin, _InputIterator __end);
      |       ^~~~~~~~
/usr/include/c++/14/bits/random.h:6375:7: note:   candidate expects 2 arguments, 3 provided
/usr/include/c++/14/bits/random.h:6372:7: note: candidate: 'template<class _IntType, class> std::seed_seq::seed_seq(std::initializer_list<_Tp>)'
 6372 |       seed_seq(std::initializer_list<_IntType> __il);
      |       ^~~~~~~~
/usr/include/c++/14/bits/random.h:6372:7: note:   candidate expects 1 argument, 3 provided
/usr/include/c++/14/bits/random.h:6367:5: note: candidate: 'std::seed_seq::seed_seq()'
 6367 |     seed_seq() noexcept
      |     ^~~~~~~~
/usr/include/c++/14/bits/random.h:6367:5: note:   candidate expects 0 arguments, 3 provided