using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using static System.Math;
using System.Text;
using System.Threading;
using System.Globalization;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using Library;

namespace Program
{
    public static class ProblemA
    {
        static bool SAIKI = false;
        static public int numberOfRandomCases = 0;
        static public void MakeTestCase(List<string> _input, List<string> _output, ref Func<string[], bool> _outputChecker)
        {
        }
        static public void Solve()
        {
            var N = NN;
            var Q = NN;
            var AList = NNList(N);
            var BList = NNList(Q);

            var F = LIB_FPS.MakeBuilder(N);
            var ans = F();
            var oneCount = AList.Count(e => e == 1);
            var excludeOne = AList.Where(e => e != 1).ToArray();

            var rt = (int)Sqrt(N);
            var q = new LIB_Deque<long[]>();
            q.PushBack(new[] { 1L });
            foreach (var item in excludeOne)
            {
                var tmp2 = new long[2];
                tmp2[0] = item - 1;
                tmp2[1] = 1;
                q.PushBack(tmp2);
            }
            while (q.Count > 1) q.PushBack(LIB_NTT.Multiply(q.PopFront(), q.PopFront()));

            ans = F(q.PopFront()) * F(0, 1).Pow(oneCount);
            foreach (var item in BList)
            {
                Console.WriteLine(ans[item]);
            }
        }
        class Printer : StreamWriter
        {
            public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
            public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; }
            public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; }
        }
        static LIB_FastIO fastio = new LIB_FastIODebug();
        static string[] args;
        static public void Main(string[] args_t) { args = args_t; if (args_t.Length == 0) { fastio = new LIB_FastIO(); Console.SetOut(new Printer(Console.OpenStandardOutput())); } if (SAIKI) { var t = new Thread(Solve, 134217728); t.Start(); t.Join(); } else Solve(); Console.Out.Flush(); }
        static long NN => fastio.Long();
        static double ND => fastio.Double();
        static string NS => fastio.Scan();
        static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray();
        static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray();
        static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray();
        static long Count<T>(this IEnumerable<T> x, Func<T, bool> pred) => Enumerable.Count(x, pred);
        static IEnumerable<T> Repeat<T>(T v, long n) => Enumerable.Repeat<T>(v, (int)n);
        static IEnumerable<int> Range(long s, long c) => Enumerable.Range((int)s, (int)c);
        static IOrderedEnumerable<T> OrderByRand<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x, _ => xorshift);
        static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x.OrderByRand(), e => e);
        static IOrderedEnumerable<T1> OrderBy<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderBy(x.OrderByRand(), selector);
        static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x) => Enumerable.OrderByDescending(x.OrderByRand(), e => e);
        static IOrderedEnumerable<T1> OrderByDescending<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderByDescending(x.OrderByRand(), selector);
        static IOrderedEnumerable<string> OrderBy(this IEnumerable<string> x) => x.OrderByRand().OrderBy(e => e, StringComparer.OrdinalIgnoreCase);
        static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderBy(selector, StringComparer.OrdinalIgnoreCase);
        static IOrderedEnumerable<string> OrderByDescending(this IEnumerable<string> x) => x.OrderByRand().OrderByDescending(e => e, StringComparer.OrdinalIgnoreCase);
        static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderByDescending(selector, StringComparer.OrdinalIgnoreCase);
        static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x);
        static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } }
        static IEnumerator<uint> _xsi = _xsc();
        static IEnumerator<uint> _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true) { var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } }
        static bool Chmax<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) < 0) { lhs = rhs; return true; } return false; }
        static bool Chmin<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) > 0) { lhs = rhs; return true; } return false; }
        static void Fill<T>(this T[] array, T value) => array.AsSpan().Fill(value);
        static void Fill<T>(this T[,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0], array.Length).Fill(value);
        static void Fill<T>(this T[,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0], array.Length).Fill(value);
        static void Fill<T>(this T[,,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0, 0], array.Length).Fill(value);
    }
}
namespace Library {
    class LIB_Deque<T>
    {
        T[] array;
        int front, cap;
        public int Count;
        public T this[long i]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get { return array[GetIndex((int)i)]; }
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            set { array[GetIndex((int)i)] = value; }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_Deque(long cap = 16)
        {
            array = new T[this.cap = (int)cap];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        int GetIndex(int i)
        {
            if (i >= cap) throw new Exception();
            var r = front + i;
            return r >= cap ? r - cap : r;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void PushFront(T x)
        {
            if (Count == cap) Extend();
            if (--front < 0) front += array.Length;
            array[front] = x;
            ++Count;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public T PopFront()
        {
            if (Count-- == 0) throw new Exception();
            var r = array[front++];
            if (front >= cap) front -= cap;
            return r;
        }
        public T Front => array[front];
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void PushBack(T x)
        {
            if (Count == cap) Extend();
            var i = front + Count++;
            array[i >= cap ? i - cap : i] = x;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public T PopBack()
        {
            if (Count == 0) throw new Exception();
            return array[GetIndex(--Count)];
        }
        public T Back => array[GetIndex(Count - 1)];
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Extend()
        {
            T[] nb = new T[cap << 1];
            if (front > cap - Count)
            {
                var l = array.Length - front; Array.Copy(array, front, nb, 0, l);
                Array.Copy(array, 0, nb, l, Count - l);
            }
            else Array.Copy(array, front, nb, 0, Count);
            array = nb; front = 0; cap <<= 1;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Insert(long i, T x)
        {
            if (i > Count) throw new Exception();
            this.PushFront(x);
            for (int j = 0; j < i; j++) this[j] = this[j + 1];
            this[i] = x;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public T RemoveAt(long i)
        {
            if (i < 0 || i >= Count) throw new Exception();
            var r = this[i];
            for (var j = i; j > 0; j--) this[j] = this[j - 1];
            this.PopFront();
            return r;
        }
    }
    class LIB_FPS
    {
        const uint MOD = 998244353;
        uint[] ary;
        public int K
        {
            get;
            private set;
        }
        public delegate LIB_FPS FPSBuilder(params long[] a);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public FPSBuilder MakeBuilder(long K) => new FPSBuilder(a => new LIB_FPS(K, a));
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FPS(long K)
        {
            this.K = (int)K;
            ary = new uint[K + 1];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FPS(long K, int[] a) : this(K, a.Select(e => (long)e).ToArray())
        {
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FPS(long K, long[] a) : this(K)
        {
            var ten = Min(ary.Length, a.Length);
            for (var i = 0; i < ten; ++i)
            {
                var val = a[i] % MOD;
                if (val < 0) val += MOD;
                ary[i] = (uint)val;
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FPS Clone()
        {
            var ret = new LIB_FPS(K);
            ret.ary = (uint[])ary.Clone();
            return ret;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator +(LIB_FPS x, LIB_FPS y)
        {
            var ret = new LIB_FPS(Max(x.K, y.K));
            for (var i = 0; i < x.ary.Length; ++i) ret.ary[i] += x.ary[i];
            for (var i = 0; i < y.ary.Length; ++i)
            {
                var sum = ret.ary[i] + y.ary[i];
                ret.ary[i] = sum >= MOD ? sum - MOD : sum;
            }
            return ret;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator +(LIB_FPS x, long y)
        {
            var ret = x.Clone();
            var sum = ret[0] + y;
            sum %= MOD;
            ret[0] = sum < 0 ? sum + MOD : sum;
            return ret;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator +(long x, LIB_FPS y) => y + x;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator -(LIB_FPS x, LIB_FPS y)
        {
            var ret = new LIB_FPS(Max(x.K, y.K));
            for (var i = 0; i < x.ary.Length; ++i) ret.ary[i] += x.ary[i];
            for (var i = 0; i < y.ary.Length; ++i)
            {
                var sum = ret.ary[i] + MOD - y.ary[i];
                ret.ary[i] = sum >= MOD ? sum - MOD : sum;
            }
            return ret;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator -(LIB_FPS x, long y)
        {
            var ret = x.Clone();
            var sum = ret[0] - y;
            sum %= MOD;
            ret[0] = sum < 0 ? sum + MOD : sum;
            return ret;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator -(long x, LIB_FPS y) => -1 * (y - x);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator *(LIB_FPS x, LIB_FPS y)
        {
            return new LIB_FPS(Max(x.K, y.K), LIB_NTT.Multiply(x.ary.Select(e => (long)e).ToArray(), y.ary.Select(e => (long)e).ToArray()));
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator *(LIB_FPS x, long y)
        {
            var ret = x.Clone();
            for (var i = 0; i < ret.ary.Length; ++i) ret.ary[i] = (uint)((MOD + y % MOD) * ret.ary[i] % MOD);
            return ret;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator *(long x, LIB_FPS y) => y * x;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator /(LIB_FPS x, LIB_FPS y) => x * y.Inverse();
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator /(LIB_FPS x, long y) => x * LIB_Mod998244353.Inverse(y);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_FPS operator /(long x, LIB_FPS y) => y.Inverse() * x;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public long BostanMori(long N, LIB_FPS nume, LIB_FPS deno)
        {
            var p = nume.ary.Select(e => (long)e).ToArray();
            var q = deno.ary.Select(e => (long)e).ToArray();
            while (N > 0)
            {
                var flipQ = q.ToArray();
                for (var i = 1; i < flipQ.Length; i += 2) flipQ[i] = flipQ[i] == 0 ? 0 : MOD - flipQ[i];
                var tmp = LIB_NTT.Multiply(p, flipQ);
                p = new long[(tmp.Length + (~N & 1)) / 2];
                for (var i = 0; i < p.Length; ++i) p[i] = tmp[i * 2 + (N & 1)];
                tmp = LIB_NTT.Multiply(q, flipQ);
                q = new long[(tmp.Length + 1) / 2];
                for (var i = 0; i < q.Length; ++i) q[i] = tmp[i * 2];
                N /= 2;
            }
            return p[0] * LIB_Mod998244353.Inverse(q[0]) % MOD;
        }
        /// <summary>
        /// べき乗
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FPS Pow(long M)
        {
            var ret = Clone();
            ret.Pow_inplace(M);
            return ret;
        }
        /// <summary>
        /// べき乗
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Pow_inplace(long M)
        {
            if (M == 0)
            {
                for (var i = 1; i < ary.Length; ++i) ary[i] = 0;
                ary[0] = 1;
                return;
            }
            if (M == 1) return;
            var l = 0;
            while (l < ary.Length && ary[l] == 0) ++l;
            if (l == ary.Length || l > (ary.Length - 1) / M)
            {
                for (var i = 0; i < ary.Length; ++i) ary[i] = 0;
                return;
            }
            var powc = LIB_Mod998244353.Pow(ary[l], M);
            var invc = LIB_Mod998244353.Inverse(ary[l]);
            var g = new LIB_FPS(K - l);
            for (var i = l; i < ary.Length; ++i) g.ary[i - l] = (uint)(ary[i] * invc % MOD);

            var dat = new List<(int idx, long val)>();
            for (var i = 1; i < g.ary.Length; ++i) if (g.ary[i] != 0) dat.Add((i, g.ary[i]));

            var ten = l * M;
            M %= MOD;
            if (dat.Count > 100)
            {
                g.Log_inplace_dense();
                for (var i = 0; i < g.ary.Length; ++i) g.ary[i] = (uint)(M * g.ary[i] % MOD);
                g.Exp_inplace_dense();
            }
            else
            {
                var inv = new long[g.ary.Length];
                inv[1] = 1;
                for (var i = 2; i < inv.Length; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;

                for (var n = 0; n < g.ary.Length - 1; ++n)
                {
                    g.ary[n + 1] = 0;
                    foreach (var item in dat)
                    {
                        if (item.idx > n + 1) break;
                        var t = item.val * g.ary[n - item.idx + 1] % MOD;
                        t = t * ((M * item.idx % MOD) - n + item.idx - 1) % MOD;
                        if (t < 0) t += MOD;
                        g.ary[n + 1] += (uint)t;
                        if (g.ary[n + 1] >= MOD) g.ary[n + 1] -= MOD;
                    }
                    g.ary[n + 1] = (uint)(g.ary[n + 1] * inv[n + 1] % MOD);
                }
            }
            for (var i = ary.Length - 1; i >= ten; --i) ary[i] = (uint)(powc * g.ary[i - ten] % MOD);
            for (var i = 0; i < ten; ++i) ary[i] = 0;
        }
        /// <summary>
        /// 指数 (a0 == 0)
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FPS Exp()
        {
            var ret = Clone();
            ret.Exp_inplace();
            return ret;
        }
        /// <summary>
        /// 指数 (a0 == 0)
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Exp_inplace()
        {
            var dat = new List<(int idx, long val)>();
            for (var i = 1; i < ary.Length; ++i) if (ary[i] != 0) dat.Add((i - 1, (long)i * ary[i] % MOD));
            if (dat.Count > 320)
            {
                Exp_inplace_dense();
                return;
            }

            // sparse
            var inv = new long[ary.Length + 1];
            inv[1] = 1;
            for (var i = 2; i < inv.Length; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
            ary[0] = 1;
            for (var n = 1; n < ary.Length; ++n)
            {
                var rhs = 0L;
                foreach (var item in dat)
                {
                    if (item.idx > n - 1) break;
                    rhs += item.val * ary[n - 1 - item.idx] % MOD;
                }
                ary[n] = (uint)((rhs % MOD) * inv[n] % MOD);
            }
        }
        /// <summary>
        /// 指数 (a0 == 0)
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Exp_inplace_dense()
        {
            var maxlen = 2;
            while ((maxlen << 1) <= K) maxlen <<= 1;
            var g = new uint[maxlen];
            var inv = new long[maxlen * 2];
            inv[1] = 1;
            for (var i = 2; i < inv.Length; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
            Span<uint> nttg = new uint[2];
            g[0] = 1;
            nttg[0] = 1;
            nttg[1] = 1;
            ary[0] = 1;
            var h_drv = Differential();

            var len = 2;
            while (len <= K)
            {
                var nextlen = len * 2;
                Span<uint> nttf = new uint[nextlen];
                for (var i = 0; i < len; ++i) nttf[i] = ary[i];
                LIB_NTT.ntt4(ref nttf);

                {
                    Span<uint> ntth = new uint[len];
                    for (var i = 0; i < len; ++i) ntth[i] = (uint)((ulong)nttf[i * 2] * nttg[i] % MOD);
                    LIB_NTT.ntt4(ref ntth, true);
                    for (var i = 0; i < len / 2; ++i) ntth[i] = ntth[i + len / 2];
                    for (var i = len / 2; i < len; ++i) ntth[i] = 0;
                    LIB_NTT.ntt4(ref ntth);
                    for (var i = 0; i < len; ++i) ntth[i] = (uint)((ulong)ntth[i] * nttg[i] % MOD);
                    LIB_NTT.ntt4(ref ntth, true);
                    for (var i = len / 2; i < len; ++i) g[i] = (ntth[i - len / 2] == 0 ? 0 : MOD - ntth[i - len / 2]);
                }

                Span<uint> t = new uint[len];
                {
                    Span<uint> ntth = new uint[len];
                    for (var i = 0; i < len - 1; ++i) ntth[i] = h_drv.ary[i];
                    LIB_NTT.ntt4(ref ntth);
                    for (var i = 0; i < len; ++i) ntth[i] = (uint)((ulong)ntth[i] * nttf[i * 2] % MOD);
                    LIB_NTT.ntt4(ref ntth, true);
                    for (var i = 1; i < len; ++i) t[i] = (uint)(((ulong)i * ary[i] + MOD - ntth[i - 1]) % MOD);
                    t[0] = ntth[len - 1] == 0 ? 0 : MOD - ntth[len - 1];
                }
                if (2 * len <= K)
                {
                    Span<uint> newt = new uint[nextlen];
                    for (var i = 0; i < len; ++i) newt[i] = t[i];
                    LIB_NTT.ntt4(ref newt);
                    nttg = new uint[nextlen];
                    for (var i = 0; i < len; ++i) nttg[i] = g[i];
                    LIB_NTT.ntt4(ref nttg);
                    for (var i = 0; i < nextlen; ++i) newt[i] = (uint)((ulong)newt[i] * nttg[i] % MOD);
                    LIB_NTT.ntt4(ref newt, true);
                    for (var i = 0; i < len; ++i) t[i] = newt[i];
                }
                else
                {
                    Span<uint> g1 = new uint[len];
                    Span<uint> s1 = new uint[len];
                    for (var i = 0; i < len / 2; ++i) g1[i] = g[i + len / 2];
                    for (var i = 0; i < len / 2; ++i) s1[i] = t[i + len / 2];
                    for (var i = len / 2; i < len; ++i) t[i] = 0;
                    LIB_NTT.ntt4(ref g1);
                    LIB_NTT.ntt4(ref s1);
                    LIB_NTT.ntt4(ref t);
                    for (var i = 0; i < len; ++i)
                    {
                        s1[i] = (uint)(((ulong)nttg[i] * s1[i] + (ulong)g1[i] * t[i]) % MOD);
                        t[i] = (uint)((ulong)nttg[i] * t[i] % MOD);
                    }
                    LIB_NTT.ntt4(ref t, true);
                    LIB_NTT.ntt4(ref s1, true);
                    for (var i = len / 2; i < len; ++i) t[i] = (t[i] + s1[i - len / 2]) % MOD;
                }

                {
                    Span<uint> ntth = new uint[nextlen];
                    var ten = Min(ary.Length, 2 * len);
                    for (var i = len; i < ten; ++i) ntth[i - len] = ary[i];
                    for (var i = 0; i < len; ++i) ntth[i] = (ntth[i] + MOD - (uint)(inv[i + len] * t[i] % MOD)) % MOD;

                    LIB_NTT.ntt4(ref ntth);
                    for (var i = 0; i < nextlen; ++i) ntth[i] = (uint)((ulong)ntth[i] * nttf[i] % MOD);
                    LIB_NTT.ntt4(ref ntth, true);

                    ten = Min(ary.Length - len, len);
                    for (var i = 0; i < ten; ++i) ary[i + len] = ntth[i];
                }

                len = nextlen;
            }
        }
        /// <summary>
        /// 対数 (a0 == 1)
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FPS Log()
        {
            var ret = Clone();
            ret.Log_inplace();
            return ret;
        }
        /// <summary>
        /// 対数 (a0 == 1)
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Log_inplace()
        {
            if (K == 0)
            {
                ary[0] = 0;
                return;
            }
            var dat = new List<(int idx, uint val)>();
            for (var i = 1; i < ary.Length; ++i) if (ary[i] != 0) dat.Add((i, ary[i]));
            if (dat.Count > 200)
            {
                Log_inplace_dense();
                return;
            }

            // sparse
            var g = new long[ary.Length - 1];
            var inv = new long[ary.Length];
            inv[1] = 1;
            for (var i = 2; i < inv.Length; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
            ary[0] = 0;
            for (var n = 0; n < ary.Length - 1; ++n)
            {
                var rhs = (long)(n + 1) * ary[n + 1] % MOD;
                foreach (var item in dat)
                {
                    if (item.idx > n) break;
                    rhs = rhs - item.val * g[n - item.idx] % MOD;
                    if (rhs < 0) rhs += MOD;
                }
                g[n] = rhs;
                ary[n + 1] = (uint)(rhs * inv[n + 1] % MOD);
            }
        }
        /// <summary>
        /// 対数 (a0 == 1)
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Log_inplace_dense()
        {
            var f2 = Differential();
            Inverse_inplace();
            var len = 1;
            while (len < ary.Length + f2.ary.Length - 1) len <<= 1;
            Span<uint> nttdiff = new uint[len];
            Span<uint> nttinv = new uint[len];
            for (var i = 0; i < f2.ary.Length; ++i) nttdiff[i] = f2.ary[i];
            for (var i = 0; i < ary.Length; ++i) nttinv[i] = ary[i];
            LIB_NTT.ntt4(ref nttdiff);
            LIB_NTT.ntt4(ref nttinv);
            for (var i = 0; i < nttinv.Length; ++i) nttinv[i] = (uint)((long)nttinv[i] * nttdiff[i] % MOD);
            LIB_NTT.ntt4(ref nttinv, true);
            for (var i = 0; i < ary.Length; ++i) ary[i] = nttinv[i];
            Integral_inplace();
        }
        /// <summary>
        /// 微分
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FPS Differential()
        {
            var ret = Clone();
            ret.Differential_inplace();
            return ret;
        }
        /// <summary>
        /// 微分
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Differential_inplace()
        {
            if (K == 0)
            {
                ary[0] = 0;
                return;
            }
            for (var i = 1L; i < ary.Length; ++i) ary[i - 1] = (uint)(i * ary[i] % MOD);
            ary[ary.Length - 1] = 0;
        }
        /// <summary>
        /// 積分
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FPS Integral()
        {
            var ret = Clone();
            ret.Integral_inplace();
            return ret;
        }
        /// <summary>
        /// 積分
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Integral_inplace()
        {
            var inv = new long[ary.Length];
            inv[1] = 1;
            for (var i = 2; i < inv.Length; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
            for (var i = ary.Length - 1; i > 0; --i) ary[i] = (uint)(inv[i] * ary[i - 1] % MOD);
            ary[0] = 0;
        }
        /// <summary>
        /// 逆元 (a0 != 0)
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FPS Inverse()
        {
            var ret = Clone();
            ret.Inverse_inplace();
            return ret;
        }
        /// <summary>
        /// 逆元 (a0 != 0)
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Inverse_inplace()
        {
            var dat = new List<(int idx, long val)>();
            for (var i = 1; i < ary.Length; ++i) if (ary[i] != 0) dat.Add((i, ary[i]));
            if (dat.Count > 160)
            {
                Inverse_inplace_dense();
                return;
            }

            // sparse
            ary[0] = (uint)LIB_Mod998244353.Inverse(ary[0]);
            for (var n = 1; n < ary.Length; ++n)
            {
                var rhs = 0L;
                foreach (var item in dat)
                {
                    if (item.idx > n) break;
                    rhs -= item.val * ary[n - item.idx] % MOD;
                }
                rhs = (rhs % MOD) * ary[0] % MOD;
                if (rhs < 0) rhs += MOD;
                ary[n] = (uint)rhs;
            }
        }
        /// <summary>
        /// 逆元 (a0 != 0)
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Inverse_inplace_dense()
        {
            var maxlen = 1;
            while (maxlen <= K) maxlen <<= 1;
            var g = new uint[maxlen];
            g[0] = (uint)LIB_Mod998244353.Inverse((long)ary[0]);
            var len = 1;
            while (len <= K)
            {
                var nextlen = len << 1;
                Span<uint> nttf = new uint[nextlen];
                Span<uint> nttg = new uint[nextlen];
                var ten = Min(nextlen, ary.Length);
                for (var i = 0; i < ten; ++i) nttf[i] = ary[i];
                for (var i = 0; i < len; ++i) nttg[i] = g[i];
                LIB_NTT.ntt4(ref nttf);
                LIB_NTT.ntt4(ref nttg);
                for (var i = 0; i < nextlen; ++i) nttf[i] = (uint)((ulong)nttf[i] * nttg[i] % MOD);
                LIB_NTT.ntt4(ref nttf, true);
                for (var i = 0; i < len; ++i) nttf[i] = 0;
                LIB_NTT.ntt4(ref nttf);
                for (var i = 0; i < nextlen; ++i) nttf[i] = (uint)((ulong)nttf[i] * nttg[i] % MOD);
                LIB_NTT.ntt4(ref nttf, true);
                for (var i = len; i < nextlen; ++i) g[i] = (nttf[i] == 0 ? 0 : MOD - nttf[i]);
                len = nextlen;
            }
            for (var i = 0; i < ary.Length; ++i) ary[i] = g[i];
        }
        public long this[long index]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get { return (long)ary[index]; }
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            set
            {
                var v = value % MOD;
                ary[index] = (uint)(v < 0 ? v + MOD : v);
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public string Join(string separator = "") => string.Join(separator, ary);
    }
    class LIB_NTT
    {
        const uint mod1 = 167772161;
        const uint root1 = 3;
        const uint mod2 = 469762049;
        const uint root2 = 3;
        const uint mod3 = 754974721;
        const uint root3 = 11;
        const uint mod4 = 998244353;
        const uint root4 = 3;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint mul1(uint x, uint y) => (uint)((ulong)x * y % mod1);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint mul2(uint x, uint y) => (uint)((ulong)x * y % mod2);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint mul3(uint x, uint y) => (uint)((ulong)x * y % mod3);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint mul4(uint x, uint y) => (uint)((ulong)x * y % mod4);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint pow1(uint x, uint n) { uint res = 1; while (n > 0) { if ((n & 1) != 0) res = mul1(res, x); x = mul1(x, x); n >>= 1; } return res; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint pow2(uint x, uint n) { uint res = 1; while (n > 0) { if ((n & 1) != 0) res = mul2(res, x); x = mul2(x, x); n >>= 1; } return res; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint pow3(uint x, uint n) { uint res = 1; while (n > 0) { if ((n & 1) != 0) res = mul3(res, x); x = mul3(x, x); n >>= 1; } return res; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint pow4(uint x, uint n) { uint res = 1; while (n > 0) { if ((n & 1) != 0) res = mul4(res, x); x = mul4(x, x); n >>= 1; } return res; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint inverse1(uint x) { long b = mod1, r = 1, u = 0, t = 0, x2 = x; while (b > 0) { var q = x2 / b; t = u; u = r - q * u; r = t; t = b; b = x2 - q * b; x2 = t; } return (uint)(r < 0 ? r + mod1 : r); }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint inverse2(uint x) { long b = mod2, r = 1, u = 0, t = 0, x2 = x; while (b > 0) { var q = x2 / b; t = u; u = r - q * u; r = t; t = b; b = x2 - q * b; x2 = t; } return (uint)(r < 0 ? r + mod2 : r); }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint inverse3(uint x) { long b = mod3, r = 1, u = 0, t = 0, x2 = x; while (b > 0) { var q = x2 / b; t = u; u = r - q * u; r = t; t = b; b = x2 - q * b; x2 = t; } return (uint)(r < 0 ? r + mod3 : r); }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint inverse4(uint x) { long b = mod4, r = 1, u = 0, t = 0, x2 = x; while (b > 0) { var q = x2 / b; t = u; u = r - q * u; r = t; t = b; b = x2 - q * b; x2 = t; } return (uint)(r < 0 ? r + mod4 : r); }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void ntt1(ref Span<uint> a, bool rev = false) { var alen = a.Length; if (alen == 1) return; var halfn = alen >> 1; Span<uint> b = new uint[alen]; var s = pow1(root1, rev ? (mod1 - 1 - (mod1 - 1) / (uint)alen) : (mod1 - 1) / (uint)alen); int i, j, k, l, r; var regLength = System.Numerics.Vector<uint>.Count; Span<uint> mods = stackalloc uint[regLength]; mods.Fill(mod1); var modV = new System.Numerics.Vector<uint>(mods); var kp = new uint[halfn + 1]; ref uint kpref = ref kp[0]; kpref = 1; for (l = 0; l < halfn; ++l) Unsafe.Add(ref kpref, l + 1) = mul1(Unsafe.Add(ref kpref, l), s); for (i = 1; i < alen; i <<= 1, l >>= 1) { for (j = 0, r = 0; j < l; ++j, r += i) { s = Unsafe.Add(ref kpref, i * j); var ten = i - regLength; var rshift = (r << 1); var rshifti = rshift + i; for (k = 0; k < ten; k += regLength) { var u = new System.Numerics.Vector<uint>(a.Slice(k + r)); var v = new System.Numerics.Vector<uint>(a.Slice(k + r + halfn)); var add = u + v; var sub = modV + u - v; var ge = System.Numerics.Vector.GreaterThanOrEqual(add, modV); add = System.Numerics.Vector.ConditionalSelect(ge, add - modV, add); add.CopyTo(b.Slice(k + rshift)); sub.CopyTo(b.Slice(k + rshifti)); } ref uint aref = ref a[0]; ref uint bref = ref b[0]; for (k = 0; k < ten; ++k) { ref uint brefi = ref Unsafe.Add(ref bref, k + rshifti); brefi = mul1(brefi, s); } for (; k < i; ++k) { var kr = k + r; ref uint akr = ref Unsafe.Add(ref aref, kr); ref uint krhalfn = ref Unsafe.Add(ref aref, kr + halfn); Unsafe.Add(ref bref, kr + r) = (akr + krhalfn) % mod1; Unsafe.Add(ref bref, kr + r + i) = mul1(akr + mod1 - krhalfn, s); } } var t = a; a = b; b = t; } if (rev) { s = inverse1((uint)alen); ref uint aref = ref a[0]; for (i = 0; i < alen; ++i) { ref uint arefi = ref Unsafe.Add(ref aref, i); arefi = mul1(arefi, s); } } }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void ntt2(ref Span<uint> a, bool rev = false) { var alen = a.Length; if (alen == 1) return; var halfn = alen >> 1; Span<uint> b = new uint[alen]; var s = pow2(root2, rev ? (mod2 - 1 - (mod2 - 1) / (uint)alen) : (mod2 - 1) / (uint)alen); int i, j, k, l, r; var regLength = System.Numerics.Vector<uint>.Count; Span<uint> mods = stackalloc uint[regLength]; mods.Fill(mod2); var modV = new System.Numerics.Vector<uint>(mods); var kp = new uint[halfn + 1]; ref uint kpref = ref kp[0]; kpref = 1; for (l = 0; l < halfn; ++l) Unsafe.Add(ref kpref, l + 1) = mul2(Unsafe.Add(ref kpref, l), s); for (i = 1; i < alen; i <<= 1, l >>= 1) { for (j = 0, r = 0; j < l; ++j, r += i) { s = Unsafe.Add(ref kpref, i * j); var ten = i - regLength; var rshift = (r << 1); var rshifti = rshift + i; for (k = 0; k < ten; k += regLength) { var u = new System.Numerics.Vector<uint>(a.Slice(k + r)); var v = new System.Numerics.Vector<uint>(a.Slice(k + r + halfn)); var add = u + v; var sub = modV + u - v; var ge = System.Numerics.Vector.GreaterThanOrEqual(add, modV); add = System.Numerics.Vector.ConditionalSelect(ge, add - modV, add); add.CopyTo(b.Slice(k + rshift)); sub.CopyTo(b.Slice(k + rshifti)); } ref uint aref = ref a[0]; ref uint bref = ref b[0]; for (k = 0; k < ten; ++k) { ref uint brefi = ref Unsafe.Add(ref bref, k + rshifti); brefi = mul2(brefi, s); } for (; k < i; ++k) { var kr = k + r; ref uint akr = ref Unsafe.Add(ref aref, kr); ref uint krhalfn = ref Unsafe.Add(ref aref, kr + halfn); Unsafe.Add(ref bref, kr + r) = (akr + krhalfn) % mod2; Unsafe.Add(ref bref, kr + r + i) = mul2(akr + mod2 - krhalfn, s); } } var t = a; a = b; b = t; } if (rev) { s = inverse2((uint)alen); ref uint aref = ref a[0]; for (i = 0; i < alen; ++i) { ref uint arefi = ref Unsafe.Add(ref aref, i); arefi = mul2(arefi, s); } } }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void ntt3(ref Span<uint> a, bool rev = false) { var alen = a.Length; if (alen == 1) return; var halfn = alen >> 1; Span<uint> b = new uint[alen]; var s = pow3(root3, rev ? (mod3 - 1 - (mod3 - 1) / (uint)alen) : (mod3 - 1) / (uint)alen); int i, j, k, l, r; var regLength = System.Numerics.Vector<uint>.Count; Span<uint> mods = stackalloc uint[regLength]; mods.Fill(mod3); var modV = new System.Numerics.Vector<uint>(mods); var kp = new uint[halfn + 1]; ref uint kpref = ref kp[0]; kpref = 1; for (l = 0; l < halfn; ++l) Unsafe.Add(ref kpref, l + 1) = mul3(Unsafe.Add(ref kpref, l), s); for (i = 1; i < alen; i <<= 1, l >>= 1) { for (j = 0, r = 0; j < l; ++j, r += i) { s = Unsafe.Add(ref kpref, i * j); var ten = i - regLength; var rshift = (r << 1); var rshifti = rshift + i; for (k = 0; k < ten; k += regLength) { var u = new System.Numerics.Vector<uint>(a.Slice(k + r)); var v = new System.Numerics.Vector<uint>(a.Slice(k + r + halfn)); var add = u + v; var sub = modV + u - v; var ge = System.Numerics.Vector.GreaterThanOrEqual(add, modV); add = System.Numerics.Vector.ConditionalSelect(ge, add - modV, add); add.CopyTo(b.Slice(k + rshift)); sub.CopyTo(b.Slice(k + rshifti)); } ref uint aref = ref a[0]; ref uint bref = ref b[0]; for (k = 0; k < ten; ++k) { ref uint brefi = ref Unsafe.Add(ref bref, k + rshifti); brefi = mul3(brefi, s); } for (; k < i; ++k) { var kr = k + r; ref uint akr = ref Unsafe.Add(ref aref, kr); ref uint krhalfn = ref Unsafe.Add(ref aref, kr + halfn); Unsafe.Add(ref bref, kr + r) = (akr + krhalfn) % mod3; Unsafe.Add(ref bref, kr + r + i) = mul3(akr + mod3 - krhalfn, s); } } var t = a; a = b; b = t; } if (rev) { s = inverse3((uint)alen); ref uint aref = ref a[0]; for (i = 0; i < alen; ++i) { ref uint arefi = ref Unsafe.Add(ref aref, i); arefi = mul3(arefi, s); } } }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public void ntt4(ref Span<uint> a, bool rev = false)
        {
            var alen = a.Length;
            if (alen == 1) return;
            var halfn = alen >> 1;
            Span<uint> b = new uint[alen];
            var s = pow4(root4, rev ? (mod4 - 1 - (mod4 - 1) / (uint)alen) : (mod4 - 1) / (uint)alen);
            int i, j, k, l, r;
            var regLength = System.Numerics.Vector<uint>.Count;
            Span<uint> mods = stackalloc uint[regLength];
            mods.Fill(mod4);
            var modV = new System.Numerics.Vector<uint>(mods);
            var kp = new uint[halfn + 1];
            ref uint kpref = ref kp[0];
            kpref = 1;
            for (l = 0; l < halfn; ++l) Unsafe.Add(ref kpref, l + 1) = mul4(Unsafe.Add(ref kpref, l), s);
            for (i = 1; i < alen; i <<= 1, l >>= 1)
            {
                for (j = 0, r = 0; j < l; ++j, r += i)
                {
                    s = Unsafe.Add(ref kpref, i * j);
                    var ten = i - regLength;
                    var rshift = (r << 1);
                    var rshifti = rshift + i;
                    for (k = 0; k < ten; k += regLength)
                    {
                        var u = new System.Numerics.Vector<uint>(a.Slice(k + r));
                        var v = new System.Numerics.Vector<uint>(a.Slice(k + r + halfn));
                        var add = u + v;
                        var sub = modV + u - v;
                        var ge = System.Numerics.Vector.GreaterThanOrEqual(add, modV);
                        add = System.Numerics.Vector.ConditionalSelect(ge, add - modV, add);
                        add.CopyTo(b.Slice(k + rshift));
                        sub.CopyTo(b.Slice(k + rshifti));
                    }
                    ref uint aref = ref a[0];
                    ref uint bref = ref b[0];
                    for (k = 0; k < ten; ++k)
                    {
                        ref uint brefi = ref Unsafe.Add(ref bref, k + rshifti);
                        brefi = mul4(brefi, s);
                    }
                    for (; k < i; ++k)
                    {
                        var kr = k + r;
                        ref uint akr = ref Unsafe.Add(ref aref, kr);
                        ref uint krhalfn = ref Unsafe.Add(ref aref, kr + halfn);
                        Unsafe.Add(ref bref, kr + r) = (akr + krhalfn) % mod4;
                        Unsafe.Add(ref bref, kr + r + i) = mul4(akr + mod4 - krhalfn, s);
                    }
                }
                var t = a; a = b; b = t;
            }
            if (rev)
            {
                s = inverse4((uint)alen);
                ref uint aref = ref a[0];
                for (i = 0; i < alen; ++i)
                {
                    ref uint arefi = ref Unsafe.Add(ref aref, i);
                    arefi = mul4(arefi, s);
                }
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public long[] NTT998244353(long[] ary, int len, bool isInverse = false)
        {
            var t = 1;
            while (t < len) t <<= 1;
            Span<uint> na = new uint[t];
            ref long aref = ref ary[0];
            ref uint naref = ref na[0];
            for (var i = 0; i < ary.Length; ++i) Unsafe.Add(ref naref, i) = (uint)Unsafe.Add(ref aref, i);
            ntt4(ref na, isInverse);
            naref = ref na[0];
            var ret = new long[t];
            ref var retref = ref ret[0];
            for (var i = 0; i < ret.Length; ++i) Unsafe.Add(ref retref, i) = Unsafe.Add(ref naref, i);
            return ret;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint[] Multiply1(uint[] a, uint[] b) { var n = a.Length + b.Length - 1; var t = 1; while (t < n) t <<= 1; Span<uint> na = new uint[t]; Span<uint> nb = new uint[t]; ref uint naref = ref na[0]; ref uint nbref = ref nb[0]; Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref naref), ref Unsafe.As<uint, byte>(ref a[0]), (uint)(a.Length << 2)); Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref nbref), ref Unsafe.As<uint, byte>(ref b[0]), (uint)(b.Length << 2)); ntt1(ref na); ntt1(ref nb); naref = ref na[0]; nbref = ref nb[0]; for (var i = 0; i < t; ++i) { ref uint narefi = ref Unsafe.Add(ref naref, i); narefi = mul1(narefi, Unsafe.Add(ref nbref, i)); } ntt1(ref na, true); var ret = new uint[n]; naref = ref na[0]; ref uint retref = ref ret[0]; for (var i = 0; i < n; ++i) Unsafe.Add(ref retref, i) = Unsafe.Add(ref naref, i); return ret; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint[] Multiply2(uint[] a, uint[] b) { var n = a.Length + b.Length - 1; var t = 1; while (t < n) t <<= 1; Span<uint> na = new uint[t]; Span<uint> nb = new uint[t]; ref uint naref = ref na[0]; ref uint nbref = ref nb[0]; Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref naref), ref Unsafe.As<uint, byte>(ref a[0]), (uint)(a.Length << 2)); Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref nbref), ref Unsafe.As<uint, byte>(ref b[0]), (uint)(b.Length << 2)); ntt2(ref na); ntt2(ref nb); naref = ref na[0]; nbref = ref nb[0]; for (var i = 0; i < t; ++i) { ref uint narefi = ref Unsafe.Add(ref naref, i); narefi = mul2(narefi, Unsafe.Add(ref nbref, i)); } ntt2(ref na, true); var ret = new uint[n]; naref = ref na[0]; ref uint retref = ref ret[0]; for (var i = 0; i < n; ++i) Unsafe.Add(ref retref, i) = Unsafe.Add(ref naref, i); return ret; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static uint[] Multiply3(uint[] a, uint[] b) { var n = a.Length + b.Length - 1; var t = 1; while (t < n) t <<= 1; Span<uint> na = new uint[t]; Span<uint> nb = new uint[t]; ref uint naref = ref na[0]; ref uint nbref = ref nb[0]; Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref naref), ref Unsafe.As<uint, byte>(ref a[0]), (uint)(a.Length << 2)); Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref nbref), ref Unsafe.As<uint, byte>(ref b[0]), (uint)(b.Length << 2)); ntt3(ref na); ntt3(ref nb); naref = ref na[0]; nbref = ref nb[0]; for (var i = 0; i < t; ++i) { ref uint narefi = ref Unsafe.Add(ref naref, i); narefi = mul3(narefi, Unsafe.Add(ref nbref, i)); } ntt3(ref na, true); var ret = new uint[n]; naref = ref na[0]; ref uint retref = ref ret[0]; for (var i = 0; i < n; ++i) Unsafe.Add(ref retref, i) = Unsafe.Add(ref naref, i); return ret; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static long[] MultiplySparse(long[] a, long[] b, long mod = -1)
        {
            if (mod == -1)
            {
                var ret = new long[a.Length + b.Length - 1];
                var data = new List<(int idx, long val)>();
                var datb = new List<(int idx, long val)>();
                for (var i = 0; i < a.Length; ++i) if (a[i] != 0) data.Add((i, a[i]));
                for (var i = 0; i < b.Length; ++i) if (b[i] != 0) datb.Add((i, b[i]));
                if (data.Count * (long)datb.Count > a.Length + b.Length)
                {
                    return null;
                }
                foreach (var item in data)
                {
                    foreach (var item2 in datb)
                    {
                        ret[item.idx + item2.idx] += item.val * item2.val;
                    }
                }
                return ret;
            }
            else
            {
                var ret = new ulong[a.Length + b.Length - 1];
                var br = new LIB_BarrettReduction((ulong)mod);
                var data = new List<(int idx, ulong val)>();
                var datb = new List<(int idx, ulong val)>();
                for (var i = 0; i < a.Length; ++i) if (a[i] != 0)
                    {
                        var v = a[i] % mod;
                        if (v < 0) v += mod;
                        data.Add((i, (ulong)v));
                    }
                for (var i = 0; i < b.Length; ++i) if (b[i] != 0)
                    {
                        var v = b[i] % mod;
                        if (v < 0) v += mod;
                        datb.Add((i, (ulong)v));
                    }
                if (data.Count * (long)datb.Count > a.Length + b.Length)
                {
                    return null;
                }
                foreach (var item in data)
                {
                    foreach (var item2 in datb)
                    {
                        ret[item.idx + item2.idx] += br.Reduce(item.val * item2.val);
                    }
                }
                return ret.Select(e => (long)(br.Reduce(e))).ToArray();
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public long[] Multiply(long[] a, long[] b)
        {
            var sparse = MultiplySparse(a, b, mod4);
            if (sparse != null) return sparse;
            var n = a.Length + b.Length - 1;
            var t = 1;
            while (t < n) t <<= 1;
            Span<uint> na = new uint[t];
            Span<uint> nb = new uint[t];
            ref long aref = ref a[0];
            ref long bref = ref b[0];
            ref uint naref = ref na[0];
            ref uint nbref = ref nb[0];
            for (var i = 0; i < a.Length; ++i) Unsafe.Add(ref naref, i) = (uint)(Unsafe.Add(ref aref, i) % mod4);
            for (var i = 0; i < b.Length; ++i) Unsafe.Add(ref nbref, i) = (uint)(Unsafe.Add(ref bref, i) % mod4);
            ntt4(ref na);
            ntt4(ref nb);
            naref = ref na[0];
            nbref = ref nb[0];
            for (var i = 0; i < t; ++i)
            {
                ref uint narefi = ref Unsafe.Add(ref naref, i);
                narefi = mul4(narefi, Unsafe.Add(ref nbref, i));
            }
            ntt4(ref na, true);
            var ret = new long[n];
            naref = ref na[0];
            ref long retref = ref ret[0];
            for (var i = 0; i < n; ++i) Unsafe.Add(ref retref, i) = Unsafe.Add(ref naref, i);
            return ret;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public long[] Multiply(long[] a, long[] b, long mod)
        {
            var sparse = MultiplySparse(a, b, mod);
            if (sparse != null) return sparse;
            if (mod == 998244353) return Multiply(a, b);
            var x = Multiply1(a.Select(e => (uint)(e % mod1)).ToArray(), b.Select(e => (uint)(e % mod1)).ToArray());
            var y = Multiply2(a.Select(e => (uint)(e % mod2)).ToArray(), b.Select(e => (uint)(e % mod2)).ToArray());
            var z = Multiply3(a.Select(e => (uint)(e % mod3)).ToArray(), b.Select(e => (uint)(e % mod3)).ToArray());
            var m1_inv_m2 = inverse2(mod1);
            var m12_inv_m3 = inverse3(mul3(mod1, mod2));
            var m12_mod = (long)mod1 * mod2 % mod;
            var ret = new long[x.Length];
            ref long retref = ref ret[0];
            ref uint xref = ref x[0];
            ref uint yref = ref y[0];
            ref uint zref = ref z[0];
            for (var i = 0; i < x.Length; ++i)
            {
                var xv = Unsafe.Add(ref xref, i);
                var v1 = mul2(Unsafe.Add(ref yref, i) + (mod2 << 1) - xv, m1_inv_m2);
                var v2 = mul3(Unsafe.Add(ref zref, i) + (mod3 << 1) - xv + mod3 - mul3(mod1, v1), m12_inv_m3);
                Unsafe.Add(ref retref, i) = (xv + ((long)mod1 * v1 % mod) + (m12_mod * v2 % mod)) % mod;
            }
            return ret;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public long[] MultiplyLong(long[] a, long[] b)
        {
            var sparse = MultiplySparse(a, b);
            if (sparse != null) return sparse;
            unchecked
            {
                const ulong mod23 = (ulong)mod2 * mod3;
                const ulong mod13 = (ulong)mod1 * mod3;
                const ulong mod12 = (ulong)mod1 * mod2;
                const ulong mod123 = (ulong)mod1 * mod2 * mod3;
                ulong[] offset = new ulong[] { 0, 0, mod123, 2 * mod123, 3 * mod123 };

                const ulong i1 = 190329765;
                const ulong i2 = 58587104;
                const ulong i3 = 187290749;

                var c1 = Multiply1(a.Select(e => (uint)(e % mod1) + mod1).ToArray(), b.Select(e => (uint)(e % mod1) + mod1).ToArray());
                var c2 = Multiply2(a.Select(e => (uint)(e % mod2) + mod2).ToArray(), b.Select(e => (uint)(e % mod2) + mod2).ToArray());
                var c3 = Multiply3(a.Select(e => (uint)(e % mod3) + mod3).ToArray(), b.Select(e => (uint)(e % mod3) + mod3).ToArray());

                var c = new long[a.Length + b.Length - 1];
                for (var i = 0; i < c.Length; ++i)
                {
                    var x = 0UL;
                    x += c1[i] * i1 % mod1 * mod23;
                    x += c2[i] * i2 % mod2 * mod13;
                    x += c3[i] * i3 % mod3 * mod12;

                    var tmp = (long)x % mod1;
                    if (tmp < 0) tmp += mod1;
                    var diff = c1[i] - tmp;
                    if (diff < 0) diff += mod1;

                    c[i] = (long)(x - offset[diff % 5]);
                }
                return c;
            }
        }
    }
    partial struct LIB_Mod998244353 : IEquatable<LIB_Mod998244353>, IEquatable<long>
    {
        const int _mod = 998244353; long v;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_Mod998244353(long x)
        {
            if (x < _mod && x >= 0) v = x;
            else if ((v = x % _mod) < 0) v += _mod;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public implicit operator LIB_Mod998244353(long x) => new LIB_Mod998244353(x);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public implicit operator long(LIB_Mod998244353 x) => x.v;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Add(LIB_Mod998244353 x) { if ((v += x.v) >= _mod) v -= _mod; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Sub(LIB_Mod998244353 x) { if ((v -= x.v) < 0) v += _mod; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Mul(LIB_Mod998244353 x) => v = (v * x.v) % _mod;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Div(LIB_Mod998244353 x) => v = (v * Inverse(x.v)) % _mod;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_Mod998244353 operator +(LIB_Mod998244353 x, LIB_Mod998244353 y) { var t = x.v + y.v; return t >= _mod ? new LIB_Mod998244353 { v = t - _mod } : new LIB_Mod998244353 { v = t }; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_Mod998244353 operator -(LIB_Mod998244353 x, LIB_Mod998244353 y) { var t = x.v - y.v; return t < 0 ? new LIB_Mod998244353 { v = t + _mod } : new LIB_Mod998244353 { v = t }; }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_Mod998244353 operator *(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v * y.v;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_Mod998244353 operator /(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v * Inverse(y.v);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public bool operator ==(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v == y.v;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public bool operator !=(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v != y.v;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public long Inverse(long x)
        {
            long b = _mod, r = 1, u = 0, t = 0;
            while (b > 0)
            {
                var q = x / b;
                t = u;
                u = r - q * u;
                r = t;
                t = b;
                b = x - q * b;
                x = t;
            }
            return r < 0 ? r + _mod : r;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Equals(LIB_Mod998244353 x) => v == x.v;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Equals(long x) => v == x;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override bool Equals(object x) => x == null ? false : Equals((LIB_Mod998244353)x);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override int GetHashCode() => v.GetHashCode();
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override string ToString() => v.ToString();
        static List<LIB_Mod998244353> _fact = new List<LIB_Mod998244353>() { 1, 1 };
        static List<LIB_Mod998244353> _inv = new List<LIB_Mod998244353>() { 0, 1 };
        static List<LIB_Mod998244353> _factinv = new List<LIB_Mod998244353>() { 1, 1 };
        static long _factm = _mod;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void B(long n)
        {
            if (_factm != _mod)
            {
                _fact = new List<LIB_Mod998244353>() { 1, 1 };
                _inv = new List<LIB_Mod998244353>() { 0, 1 };
                _factinv = new List<LIB_Mod998244353>() { 1, 1 };
            }
            if (n >= _fact.Count)
            {
                for (int i = _fact.Count; i <= n; ++i)
                {
                    _fact.Add(_fact[i - 1] * i);
                    _inv.Add(_mod - _inv[(int)(_mod % i)] * (_mod / i));
                    _factinv.Add(_factinv[i - 1] * _inv[i]);
                }
            }
            _factm = _mod;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_Mod998244353 Comb(long n, long k)
        {
            B(n);
            if (n == 0 && k == 0) return 1;
            if (n < k || n < 0) return 0;
            return _fact[(int)n] * _factinv[(int)(n - k)] * _factinv[(int)k];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_Mod998244353 CombOK(long n, long k)
        {
            LIB_Mod998244353 ret = 1;
            LIB_Mod998244353 deno = 1;
            var chk = n - k;
            if (chk < k) k = chk;
            for (var i = 0; i < k; i++) ret *= n - i;
            for (var i = 1; i <= k; i++) deno *= i;
            return ret / deno;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_Mod998244353 Perm(long n, long k)
        {
            B(n);
            if (n == 0 && k == 0) return 1;
            if (n < k || n < 0) return 0;
            return _fact[(int)n] * _factinv[(int)(n - k)];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_Mod998244353 KanzenPerm(long n, long k) => Enumerable.Range(0, (int)k + 1).Aggregate((LIB_Mod998244353)0, (a, e) => a + (1 - ((e & 1) << 1)) * LIB_Mod998244353.Comb(k, e) * LIB_Mod998244353.Perm(n - e, k - e));
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static public LIB_Mod998244353 Pow(LIB_Mod998244353 x, long y)
        {
            LIB_Mod998244353 a = 1;
            while (y != 0)
            {
                if ((y & 1) == 1) a.Mul(x);
                x.Mul(x);
                y >>= 1;
            }
            return a;
        }
    }
    class LIB_BarrettReduction
    {
        ulong MOD;
        ulong mh;
        ulong ml;
        const ulong ALL1_32 = (ulong)~0U;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_BarrettReduction(ulong mod)
        {
            MOD = mod;
            var m = ~0UL / MOD;
            unchecked { if (m * MOD + MOD == 0) ++m; }
            mh = m >> 32;
            ml = m & ALL1_32;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public ulong Reduce(ulong x)
        {
            var z = (x & ALL1_32) * ml;
            z = (x & ALL1_32) * mh + (x >> 32) * ml + (z >> 32);
            z = (x >> 32) * mh + (z >> 32);
            x -= z * MOD;
            return x < MOD ? x : x - MOD;
        }
    }
    class LIB_FastIO
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FastIO() { str = Console.OpenStandardInput(); }
        readonly Stream str;
        readonly byte[] buf = new byte[2048];
        int len, ptr;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        byte read()
        {
            if (ptr >= len)
            {
                ptr = 0;
                if ((len = str.Read(buf, 0, 2048)) <= 0)
                {
                    return 0;
                }
            }
            return buf[ptr++];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        char Char()
        {
            byte b = 0;
            do b = read();
            while (b < 33 || 126 < b);
            return (char)b;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        virtual public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        virtual public long Long()
        {
            long ret = 0; byte b = 0; var ng = false;
            do b = read();
            while (b != '-' && (b < '0' || '9' < b));
            if (b == '-') { ng = true; b = read(); }
            for (; true; b = read())
            {
                if (b < '0' || '9' < b)
                    return ng ? -ret : ret;
                else ret = (ret << 3) + (ret << 1) + b - '0';
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        virtual public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }
    }
    class LIB_FastIODebug : LIB_FastIO
    {
        Queue<string> param = new Queue<string>();
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue(); }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FastIODebug() { }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override string Scan() => NextString();
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override long Long() => long.Parse(NextString());
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override double Double() => double.Parse(NextString());
    }
}