Submission #31473003

---

Source Code Expand

using AtCoder;
using AtCoder.Internal;
using AtCoder.Operators;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using ModInt = AtCoder.StaticModInt<AtCoder.Mod998244353>;
using System;
using System.Buffers;
using System.Buffers.Text;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;
using System.Text;
using static System.Math;
using 凾 = System.Runtime.CompilerServices.MethodImplAttribute;
partial class Program
{
    const bool __ManyTestCases = false;
#if !LOCAL_RUNNING
    static void Main()=>new Program(new PropertyConsoleReader(),new Utf8ConsoleWriter()).Run();
    [凾(256)]
#endif
    private ConsoleOutput? Calc()
    {
        int N = cr;
        int K = N - cr.Int + 1;
        var LR = cr.Repeat(N).Select<(int L, int R, ModInt Inv)>(cr =>
         {
             int l = cr;
             int r = cr;
             return (l, r, ModInt.Raw(r - l).Inv());
         });
        var nums = LR.SelectMany(t => new[] { t.L, t.R }).Distinct().ToArray().Sort();
        var fpsOne = new FormalPowerSeries<Mod998244353>(stackalloc ModInt[] { ModInt.Raw(1) });

        ModInt sum = default;

        // https://atcoder.jp/contests/hhkb2020/submissions/31466098
        // と同じような雰囲気で解ける
        for (int h = 0; h + 1 < nums.Length; h++)
        {
            var cur = nums[h];
            var nex = nums[h + 1];

            var dp = new FormalPowerSeries<Mod998244353>[] { fpsOne };
            foreach (var (l, r, inv) in LR)
            {
                if (nex <= l) continue;
                Array.Resize(ref dp, Min(K, dp.Length) + 1);
                if (r <= cur)
                {
                    for (int i = dp.Length - 1; i > 0; i--)
                        dp[i] = dp[i - 1];
                    dp[0] = fpsOne;
                    continue;
                }

                var left = new FormalPowerSeries<Mod998244353>(new ModInt[] { -l * inv, inv });
                var right = new FormalPowerSeries<Mod998244353>(new ModInt[] { r * inv, -inv });

                for (int i = dp.Length - 1; i > 0; i--)
                {
                    if (dp[i] != null)
                        dp[i] += (dp[i - 1] - dp[i]) * left;
                    else
                        dp[i] = dp[i - 1] * left;
                }
            }
            if (dp.GetOrDummy(K) is { } p)
            {
                p = p.Derivative();
                p <<= 1;
                p = p.Integrate();

                sum += p.Eval(nex) - p.Eval(cur);
            }
        }

        return sum.Value;
    }
    FormalPowerSeries<Mod998244353> fpsZero = new FormalPowerSeries<Mod998244353>(Array.Empty<ModInt>());
}
#region Expanded by https://github.com/kzrnm/SourceExpander
//LICENSE:
//https://github.com/kzrnm/Kzrnm.Competitive/blob/master/LICENSE
//https://github.com/kzrnm/Kzrnm.Competitive/blob/master/3rd-party%20Licenses.txt
#pragma warning disable
namespace AtCoder.Internal{public static class InternalBit{[凾(256)]public static uint ExtractLowestSetBit(int n){if(Bmi1.IsSupported){return Bmi1.ExtractLowestSetBit((uint)n);}return(uint)(n&-n);}[凾(256)]public static int BSF(uint n){return BitOperations.TrailingZeroCount(n);}[凾(256)]public static int CeilPow2(int n){var un=(uint)n;if(un<=1)return 0;return BitOperations.Log2(un-1)+1;}}}
namespace AtCoder.Internal{public class Barrett{public readonly uint Mod;internal readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1;}[凾(256)]public uint Mul(uint a,uint b){var z=(ulong)a*b;if(Bmi2.X64.IsSupported){var x=Bmi2.X64.MultiplyNoFlags(z,IM);var v=unchecked((uint)(z-x*Mod));if(Mod<=v)v+=Mod;return v;}return(uint)(z%Mod);}}}
namespace AtCoder.Internal{public static class Butterfly<T>where T:struct,IStaticMod{internal static readonly StaticModInt<T>[]sumE=CalcurateSumE();internal static readonly StaticModInt<T>[]sumIE=CalcurateSumIE();public static void Calculate(Span<StaticModInt<T>>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector<uint>.Count;var modV=new Vector<uint>(default(T).Mod);for(int ph=1;ph<=h;ph++){int w=1<<(ph-1);int p=1<<(h-ph);var now=StaticModInt<T>.Raw(1);for(int s=0;s<w;s++){int offset=s<<(h-ph+1);var ls=a.Slice(offset,p);var rs=a.Slice(offset+p,p);if(p<regLength){for(int i=0;i<p;i++){var l=ls[i];var r=rs[i]*now;ls[i]=l+r;rs[i]=l-r;}}else{foreach(ref var r in rs){r*=now;}var lu=MemoryMarshal.Cast<StaticModInt<T>,uint>(ls);var ru=MemoryMarshal.Cast<StaticModInt<T>,uint>(rs);for(int i=0;i<lu.Length;i+=regLength){var luSliced=lu.Slice(i);var ruSliced=ru.Slice(i);var u=new Vector<uint>(luSliced);var v=new Vector<uint>(ruSliced);var add=u+v;var sub=u-v;var ge=Vector.GreaterThanOrEqual(add,modV);add=Vector.ConditionalSelect(ge,add-modV,add);ge=Vector.GreaterThanOrEqual(sub,modV);sub=Vector.ConditionalSelect(ge,sub+modV,sub);add.CopyTo(luSliced);sub.CopyTo(ruSliced);}}now*=sumE[InternalBit.BSF(~(uint)s)];}}}public static void CalculateInv(Span<StaticModInt<T>>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector<uint>.Count;var modV=new Vector<uint>(default(T).Mod);for(int ph=h;ph>=1;ph--){int w=1<<(ph-1);int p=1<<(h-ph);var iNow=StaticModInt<T>.Raw(1);for(int s=0;s<w;s++){int offset=s<<(h-ph+1);var ls=a.Slice(offset,p);var rs=a.Slice(offset+p,p);if(p<regLength){for(int i=0;i<p;i++){var l=ls[i];var r=rs[i];ls[i]=l+r;rs[i]=StaticModInt<T>.Raw((int)((ulong)(default(T).Mod+l.Value-r.Value)*(ulong)iNow.Value%default(T).Mod));}}else{var lu=MemoryMarshal.Cast<StaticModInt<T>,uint>(ls);var ru=MemoryMarshal.Cast<StaticModInt<T>,uint>(rs);for(int i=0;i<lu.Length;i+=regLength){var luSliced=lu.Slice(i);var ruSliced=ru.Slice(i);var u=new Vector<uint>(luSliced);var v=new Vector<uint>(ruSliced);var add=u+v;var sub=u-v;var ge=Vector.GreaterThanOrEqual(add,modV);add=Vector.ConditionalSelect(ge,add-modV,add);sub+=modV;add.CopyTo(luSliced);sub.CopyTo(ruSliced);}foreach(ref var r in rs){r*=iNow;}}iNow*=sumIE[InternalBit.BSF(~(uint)s)];}}}private static StaticModInt<T>[]CalcurateSumE(){int g=InternalMath.PrimitiveRoot<T>();int cnt2=InternalBit.BSF(default(T).Mod-1);var e=new StaticModInt<T>(g).Pow((default(T).Mod-1)>>cnt2);var ie=e.Inv();var sumE=new StaticModInt<T>[30];Span<StaticModInt<T>>es=stackalloc StaticModInt<T>[cnt2-1];Span<StaticModInt<T>>ies=stackalloc StaticModInt<T>[cnt2-1];for(int i=es.Length-1;i>=0;i--){es[i]=e;ies[i]=ie;e*=e;ie*=ie;}var now=StaticModInt<T>.Raw(1);for(int i=0;i<=cnt2-2;i++){sumE[i]=es[i]*now;now*=ies[i];}return sumE;}private static StaticModInt<T>[]CalcurateSumIE(){int g=InternalMath.PrimitiveRoot<T>();int cnt2=InternalBit.BSF(default(T).Mod-1);var e=new StaticModInt<T>(g).Pow((default(T).Mod-1)>>cnt2);var ie=e.Inv();var sumIE=new StaticModInt<T>[30];Span<StaticModInt<T>>es=stackalloc StaticModInt<T>[cnt2-1];Span<StaticModInt<T>>ies=stackalloc StaticModInt<T>[cnt2-1];for(int i=es.Length-1;i>=0;i--){es[i]=e;ies[i]=ie;e*=e;ie*=ie;}var now=StaticModInt<T>.Raw(1);for(int i=0;i<=cnt2-2;i++){sumIE[i]=ies[i]*now;now*=es[i];}return sumIE;}[Conditional("ATCODER_CONTRACT")]private static void CheckPow2(int n){if(BitOperations.PopCount((uint)n)!=1){throw new ArgumentException("配列長は2のべき乗でなければなりません。");}}}}
namespace AtCoder.Internal{public static class InternalMath{private static readonly Dictionary<uint,int>primitiveRootsCache=new Dictionary<uint,int>(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};[凾(256)]public static int PrimitiveRoot<TMod>()where TMod:struct,IStaticMod{uint m=default(TMod).Mod;if(primitiveRootsCache.TryGetValue(m,out var p)){return p;}return primitiveRootsCache[m]=PrimitiveRootCalculate<TMod>();}static int PrimitiveRootCalculate<TMod>()where TMod:struct,IStaticMod{int m=(int)default(TMod).Mod;Span<int>divs=stackalloc int[20];divs[0]=2;int cnt=1;int x=(m-1)/2;while(x%2==0){x>>=1;}for(int i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;while(x%i==0){x/=i;}}}if(x>1){divs[cnt++]=x;}divs=divs.Slice(0,cnt);for(int g=2;;g++){foreach(var d in divs)if(new StaticModInt<TMod>(g).Pow((m-1)/d).Value==1)goto NEXT;return g;NEXT:{}}}[凾(256)]public static(long,long)InvGCD(long a,long b){a=SafeMod(a,b);if(a==0)return(b,0);long s=b,t=a;long m0=0,m1=1;long u;while(true){if(t==0){if(m0<0)m0+=b/s;return(s,m0);}u=s/t;s-=t*u;m0-=m1*u;if(s==0){if(m1<0)m1+=b/t;return(t,m1);}u=t/s;t-=s*u;m1-=m0*u;}}[凾(256)]public static long SafeMod(long x,long m){x%=m;if(x<0)x+=m;return x;}[凾(256)]public static bool IsPrime(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long d=n-1;while(d%2==0)d/=2;ReadOnlySpan<byte>bases=stackalloc byte[3]{2,7,61};foreach(long a in bases){long t=d;long y=PowMod(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0){return false;}}return true;}[凾(256)]private static long PowMod(long x,long n,int m){if(m==1)return 0;Barrett barrett=new Barrett((uint)m);uint r=1,y=(uint)SafeMod(x,m);while(0<n){if((n&1)!=0)r=barrett.Mul(r,y);y=barrett.Mul(y,y);n>>=1;}return r;}[凾(256)]public static ulong FloorSumUnsigned(ulong n,ulong m,ulong a,ulong b){ulong ans=0;while(true){if(a>=m){ans+=(n-1)*n/2*(a/m);a%=m;}if(b>=m){ans+=n*(b/m);b%=m;}ulong yMax=a*n+b;if(yMax<m)return ans;(n,m,a,b)=(yMax/m,a,m,yMax%m);}}}}
namespace AtCoder{public static partial class MathLib{[凾(256)]public static StaticModInt<TMod>[]Convolution<TMod>(StaticModInt<TMod>[]a,StaticModInt<TMod>[]b)where TMod:struct,IStaticMod=>Convolution((ReadOnlySpan<StaticModInt<TMod>>)a,b);[凾(256)]public static StaticModInt<TMod>[]Convolution<TMod>(ReadOnlySpan<StaticModInt<TMod>>a,ReadOnlySpan<StaticModInt<TMod>>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0)return Array.Empty<StaticModInt<TMod>>();if(Math.Min(n,m)<=60)return ConvolutionNaive(a,b);return ConvolutionFFT(a,b);}[凾(256)]private static StaticModInt<TMod>[]ConvolutionFFT<TMod>(ReadOnlySpan<StaticModInt<TMod>>a,ReadOnlySpan<StaticModInt<TMod>>b)where TMod:struct,IStaticMod{int n=a.Length,m=b.Length;int z=1<<InternalBit.CeilPow2(n+m-1);var a2=new StaticModInt<TMod>[z];var b2=new StaticModInt<TMod>[z];a.CopyTo(a2);b.CopyTo(b2);var result=ConvolutionFFTInner(a2,b2);Array.Resize(ref result,n+m-1);var iz=new StaticModInt<TMod>(z).Inv();for(int i=0;i<result.Length;i++)result[i]*=iz;return result;}[凾(256)]private static StaticModInt<TMod>[]ConvolutionFFTInner<TMod>(StaticModInt<TMod>[]a,StaticModInt<TMod>[]b)where TMod:struct,IStaticMod{Butterfly<TMod>.Calculate(a);Butterfly<TMod>.Calculate(b);for(int i=0;i<a.Length;i++)a[i]*=b[i];Butterfly<TMod>.CalculateInv(a);return a;}[凾(256)]private static StaticModInt<TMod>[]ConvolutionNaive<TMod>(ReadOnlySpan<StaticModInt<TMod>>a,ReadOnlySpan<StaticModInt<TMod>>b)where TMod:struct,IStaticMod{if(a.Length<b.Length){var temp=a;a=b;b=temp;}var ans=new StaticModInt<TMod>[a.Length+b.Length-1];for(int i=0;i<a.Length;i++){for(int j=0;j<b.Length;j++){ans[i+j]+=a[i]*b[j];}}return ans;}[凾(256)]public static long[]ConvolutionLong(ReadOnlySpan<long>a,ReadOnlySpan<long>b){unchecked{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<long>();}const ulong Mod1=754974721;const ulong Mod2=167772161;const ulong Mod3=469762049;const ulong M2M3=Mod2*Mod3;const ulong M1M3=Mod1*Mod3;const ulong M1M2=Mod1*Mod2;const ulong M1M2M3=Mod1*Mod2*Mod3;const ulong i1=190329765;const ulong i2=58587104;const ulong i3=187290749;var c1=Convolution<FFTMod1>(a,b);var c2=Convolution<FFTMod2>(a,b);var c3=Convolution<FFTMod3>(a,b);var c=new long[n+m-1];for(int i=0;i<c.Length;i++){ulong x=0;x+=((ulong)c1[i]*i1)%Mod1*M2M3;x+=((ulong)c2[i]*i2)%Mod2*M1M3;x+=((ulong)c3[i]*i3)%Mod3*M1M2;long diff=c1[i]-InternalMath.SafeMod((long)x,(long)Mod1);if(diff<0){diff+=(long)Mod1;}switch(diff%5){case 2:x-=M1M2M3;break;case 3:x-=2*M1M2M3;break;case 4:x-=3*M1M2M3;break;}c[i]=(long)x;}return c;}}private readonly struct FFTMod1:IStaticMod{public uint Mod=>754974721;public bool IsPrime=>true;}private readonly struct FFTMod2:IStaticMod{public uint Mod=>167772161;public bool IsPrime=>true;}private readonly struct FFTMod3:IStaticMod{public uint Mod=>469762049;public bool IsPrime=>true;}}}
namespace AtCoder{public static partial class MathLib{[凾(256)]public static Int32[]Convolution(Int32[]a,Int32[]b)=>Convolution<Mod998244353>(a,b);[凾(256)]public static Int32[]Convolution<TMod>(Int32[]a,Int32[]b)where TMod:struct,IStaticMod=>Convolution<TMod>(a.AsSpan(),b.AsSpan());[凾(256)]public static Int32[]Convolution<TMod>(ReadOnlySpan<Int32>a,ReadOnlySpan<Int32>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<Int32>();}var a2=new StaticModInt<TMod>[n];var b2=new StaticModInt<TMod>[m];for(int i=0;i<a2.Length;i++){a2[i]=new StaticModInt<TMod>(a[i]);}for(int i=0;i<b2.Length;i++){b2[i]=new StaticModInt<TMod>(b[i]);}var c2=Convolution(a2,b2);var c=new Int32[n+m-1];for(int i=0;i<c.Length;i++){c[i]=(Int32)c2[i].Value;}return c;}[凾(256)]public static UInt32[]Convolution(UInt32[]a,UInt32[]b)=>Convolution<Mod998244353>(a,b);[凾(256)]public static UInt32[]Convolution<TMod>(UInt32[]a,UInt32[]b)where TMod:struct,IStaticMod=>Convolution<TMod>(a.AsSpan(),b.AsSpan());[凾(256)]public static UInt32[]Convolution<TMod>(ReadOnlySpan<UInt32>a,ReadOnlySpan<UInt32>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<UInt32>();}var a2=new StaticModInt<TMod>[n];var b2=new StaticModInt<TMod>[m];for(int i=0;i<a2.Length;i++){a2[i]=new StaticModInt<TMod>(a[i]);}for(int i=0;i<b2.Length;i++){b2[i]=new StaticModInt<TMod>(b[i]);}var c2=Convolution(a2,b2);var c=new UInt32[n+m-1];for(int i=0;i<c.Length;i++){c[i]=(UInt32)c2[i].Value;}return c;}[凾(256)]public static Int64[]Convolution(Int64[]a,Int64[]b)=>Convolution<Mod998244353>(a,b);[凾(256)]public static Int64[]Convolution<TMod>(Int64[]a,Int64[]b)where TMod:struct,IStaticMod=>Convolution<TMod>(a.AsSpan(),b.AsSpan());[凾(256)]public static Int64[]Convolution<TMod>(ReadOnlySpan<Int64>a,ReadOnlySpan<Int64>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<Int64>();}var a2=new StaticModInt<TMod>[n];var b2=new StaticModInt<TMod>[m];for(int i=0;i<a2.Length;i++){a2[i]=new StaticModInt<TMod>(a[i]);}for(int i=0;i<b2.Length;i++){b2[i]=new StaticModInt<TMod>(b[i]);}var c2=Convolution(a2,b2);var c=new Int64[n+m-1];for(int i=0;i<c.Length;i++){c[i]=(Int64)c2[i].Value;}return c;}[凾(256)]public static UInt64[]Convolution(UInt64[]a,UInt64[]b)=>Convolution<Mod998244353>(a,b);[凾(256)]public static UInt64[]Convolution<TMod>(UInt64[]a,UInt64[]b)where TMod:struct,IStaticMod=>Convolution<TMod>(a.AsSpan(),b.AsSpan());[凾(256)]public static UInt64[]Convolution<TMod>(ReadOnlySpan<UInt64>a,ReadOnlySpan<UInt64>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<UInt64>();}var a2=new StaticModInt<TMod>[n];var b2=new StaticModInt<TMod>[m];for(int i=0;i<a2.Length;i++){a2[i]=new StaticModInt<TMod>(a[i]);}for(int i=0;i<b2.Length;i++){b2[i]=new StaticModInt<TMod>(b[i]);}var c2=Convolution(a2,b2);var c=new UInt64[n+m-1];for(int i=0;i<c.Length;i++){c[i]=(UInt64)c2[i].Value;}return c;}}}
namespace AtCoder{public static partial class MathLib{[凾(256)]public static(long y,long m)CRT(long[]r,long[]m){long r0=0,m0=1;for(int i=0;i<m.Length;i++){long r1=InternalMath.SafeMod(r[i],m[i]);long m1=m[i];if(m0<m1){(r0,r1)=(r1,r0);(m0,m1)=(m1,m0);}if(m0%m1==0){if(r0%m1!=r1)return(0,0);continue;}var(g,im)=InternalMath.InvGCD(m0,m1);long u1=(m1/g);if((r1-r0)%g!=0)return(0,0);long x=(r1-r0)/g%u1*im%u1;r0+=x*m0;m0*=u1;if(r0<0)r0+=m0;}return(r0,m0);}}}
namespace AtCoder{public static partial class MathLib{[凾(256)]public static long FloorSum(long n,long m,long a,long b){var nn=(ulong)n;var mm=(ulong)m;ulong aa,bb;ulong ans=0;if(a<0){var a2=(ulong)InternalMath.SafeMod(a,m);ans-=nn*(nn-1)/2*((a2-(ulong)a)/mm);aa=a2;}else aa=(ulong)a;if(b<0){var b2=(ulong)InternalMath.SafeMod(b,m);ans-=nn*((b2-(ulong)b)/mm);bb=b2;}else bb=(ulong)b;return(long)(ans+InternalMath.FloorSumUnsigned(nn,mm,aa,bb));}}}
namespace AtCoder{public static partial class MathLib{[凾(256)]public static long InvMod(long x,long m){var(g,res)=InternalMath.InvGCD(x,m);return res;}}}
namespace AtCoder{public static partial class MathLib{[凾(256)]public static long PowMod(long x,long n,int m){if(m==1)return 0;Barrett barrett=new Barrett((uint)m);uint r=1,y=(uint)InternalMath.SafeMod(x,m);while(0<n){if((n&1)!=0)r=barrett.Mul(r,y);y=barrett.Mul(y,y);n>>=1;}return r;}}}
namespace AtCoder{public interface IStaticMod{uint Mod{get;}bool IsPrime{get;}}public readonly struct Mod1000000007:IStaticMod{public uint Mod=>1000000007;public bool IsPrime=>true;}public readonly struct Mod998244353:IStaticMod{public uint Mod=>998244353;public bool IsPrime=>true;}public readonly struct StaticModIntOperator<T>:IArithmeticOperator<StaticModInt<T>>where T:struct,IStaticMod{public StaticModInt<T>MultiplyIdentity=>StaticModInt<T>.Raw(1);[凾(256)]public StaticModInt<T>Add(StaticModInt<T>x,StaticModInt<T>y)=>x+y;[凾(256)]public StaticModInt<T>Subtract(StaticModInt<T>x,StaticModInt<T>y)=>x-y;[凾(256)]public StaticModInt<T>Multiply(StaticModInt<T>x,StaticModInt<T>y)=>x*y;[凾(256)]public StaticModInt<T>Divide(StaticModInt<T>x,StaticModInt<T>y)=>x/y;[凾(256)]StaticModInt<T>IDivisionOperator<StaticModInt<T>>.Modulo(StaticModInt<T>x,StaticModInt<T>y)=>throw new NotSupportedException();[凾(256)]public StaticModInt<T>Minus(StaticModInt<T>x)=>-x;[凾(256)]public StaticModInt<T>Increment(StaticModInt<T>x)=> ++x;[凾(256)]public StaticModInt<T>Decrement(StaticModInt<T>x)=> --x;}public readonly struct StaticModInt<T>:IEquatable<StaticModInt<T>>where T:struct,IStaticMod{internal readonly uint _v;private static readonly T op=default;public int Value=>(int)_v;public static int Mod=>(int)op.Mod;[凾(256)]public static StaticModInt<T>Raw(int v){var u=unchecked((uint)v);return new StaticModInt<T>(u);}[凾(256)]public StaticModInt(long v):this(Round(v)){}[凾(256)]public StaticModInt(ulong v):this((uint)(v%op.Mod)){}[凾(256)]private StaticModInt(uint v)=>_v=v;[凾(256)]private static uint Round(long v){var x=v%op.Mod;if(x<0){x+=op.Mod;}return(uint)x;}[凾(256)]public static StaticModInt<T>operator ++(StaticModInt<T>value){var v=value._v+1;if(v==op.Mod){v=0;}return new StaticModInt<T>(v);}[凾(256)]public static StaticModInt<T>operator --(StaticModInt<T>value){var v=value._v;if(v==0){v=op.Mod;}return new StaticModInt<T>(v-1);}[凾(256)]public static StaticModInt<T>operator+(StaticModInt<T>lhs,StaticModInt<T>rhs){var v=lhs._v+rhs._v;if(v>=op.Mod){v-=op.Mod;}return new StaticModInt<T>(v);}[凾(256)]public static StaticModInt<T>operator-(StaticModInt<T>lhs,StaticModInt<T>rhs){unchecked{var v=lhs._v-rhs._v;if(v>=op.Mod){v+=op.Mod;}return new StaticModInt<T>(v);}}[凾(256)]public static StaticModInt<T>operator*(StaticModInt<T>lhs,StaticModInt<T>rhs)=>new StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));[凾(256)]public static StaticModInt<T>operator/(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs*rhs.Inv();[凾(256)]public static StaticModInt<T>operator+(StaticModInt<T>value)=>value;[凾(256)]public static StaticModInt<T>operator-(StaticModInt<T>value)=>new StaticModInt<T>(value._v==0?0:op.Mod-value._v);[凾(256)]public static bool operator==(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v==rhs._v;[凾(256)]public static bool operator!=(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v!=rhs._v;[凾(256)]public static implicit operator StaticModInt<T>(int value)=>new StaticModInt<T>(value);[凾(256)]public static implicit operator StaticModInt<T>(long value)=>new StaticModInt<T>(value);[凾(256)]public StaticModInt<T>Pow(long n){var x=this;var r=new StaticModInt<T>(1U);while(n>0){if((n&1)>0){r*=x;}x*=x;n>>=1;}return r;}[凾(256)]public StaticModInt<T>Inv(){if(op.IsPrime){return Pow(op.Mod-2);}else{var(g,x)=InternalMath.InvGCD(_v,op.Mod);return new StaticModInt<T>(x);}}public override string ToString()=>_v.ToString();public override bool Equals(object obj)=>obj is StaticModInt<T>m&&Equals(m);[凾(256)]public bool Equals(StaticModInt<T>other)=>_v==other._v;public override int GetHashCode()=>_v.GetHashCode();}}
namespace AtCoder.Operators{public interface IAdditionOperator<T>{T Add(T x,T y);}public interface ISubtractOperator<T>{T Subtract(T x,T y);}public interface IMultiplicationOperator<T>{T Multiply(T x,T y);T MultiplyIdentity{get;}}public interface IDivisionOperator<T>:IMultiplicationOperator<T>{T Divide(T x,T y);T Modulo(T x,T y);}public interface IUnaryNumOperator<T>{T Minus(T x);T Increment(T x);T Decrement(T x);}public interface IArithmeticOperator<T>:IAdditionOperator<T>,ISubtractOperator<T>,IMultiplicationOperator<T>,IDivisionOperator<T>,IUnaryNumOperator<T>{}public interface ICompareOperator<T>:IComparer<T>{bool GreaterThan(T x,T y);bool GreaterThanOrEqual(T x,T y);bool LessThan(T x,T y);bool LessThanOrEqual(T x,T y);}public interface IMinMaxValue<T>{T MinValue{get;}T MaxValue{get;}}public interface INumOperator<T>:IArithmeticOperator<T>,ICompareOperator<T>,IMinMaxValue<T>{}public interface IShiftOperator<T>{T LeftShift(T x,int y);T RightShift(T x,int y);}}
namespace Kzrnm.Competitive.IO{using _R=PropertyConsoleReader;using static Utf8Parser;public sealed class PropertyConsoleReader{internal const int BufSize=1<<12;private readonly Stream input;private readonly Encoding encoding;internal readonly byte[]buf=new byte[BufSize];internal int pos;internal int len;[凾(256)]public PropertyConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding){}[凾(256)]public PropertyConsoleReader(Stream input,Encoding encoding){this.input=input;this.encoding=encoding;}[凾(256)]private void FillEntireNumber(){if((uint)pos>=(uint)buf.Length)FillNextBuffer();while(buf[pos]<=' ')if( ++pos>=len)FillNextBuffer();if(pos+21>=buf.Length&&buf[buf.Length-1]>' ')FillEntireNumberImpl();}private void FillEntireNumberImpl(){buf.AsSpan(pos,len-pos).CopyTo(buf);len-=pos;pos=0;var numberOfBytes=input.Read(buf,len,buf.Length-len);if(numberOfBytes==0)buf[len++]=10;else if(numberOfBytes+len<buf.Length)buf[buf.Length-1]=10;len+=numberOfBytes;}private void FillNextBuffer(){if((len=input.Read(buf,0,buf.Length))==0){buf[0]=10;len=1;}else if(len<buf.Length)buf[buf.Length-1]=10;pos=0;}[凾(256)]internal byte Read(){if(pos>=len)FillNextBuffer();return buf[pos++];}public int Int{[凾(256)]get{FillEntireNumber();TryParse(buf.AsSpan(pos),out int v,out int bc);pos+=bc;return v;}}public int Int0{[凾(256)]get=>Int-1;}public uint UInt{[凾(256)]get{FillEntireNumber();TryParse(buf.AsSpan(pos),out uint v,out int bc);pos+=bc;return v;}}public uint UInt0{[凾(256)]get=>UInt-1;}public long Long{[凾(256)]get{FillEntireNumber();TryParse(buf.AsSpan(pos),out long v,out int bc);pos+=bc;return v;}}public long Long0{[凾(256)]get=>Long-1;}public ulong ULong{[凾(256)]get{FillEntireNumber();TryParse(buf.AsSpan(pos),out ulong v,out int bc);pos+=bc;return v;}}public ulong ULong0{[凾(256)]get=>ULong-1;}public double Double{[凾(256)]get{FillEntireNumber();TryParse(buf.AsSpan(pos),out double v,out int bc);pos+=bc;return v;}}public decimal Decimal{[凾(256)]get{FillEntireNumber();TryParse(buf.AsSpan(pos),out decimal v,out int bc);pos+=bc;return v;}}public string String{[凾(256)]get{var sb=new List<byte>();;byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(' '<b);return encoding.GetString(sb.ToArray());}}public string Ascii{[凾(256)]get{var sb=new StringBuilder();byte b;do b=Read();while(b<=' ');do{sb.Append((char)b);b=Read();}while(' '<b);return sb.ToString();}}public string Line{[凾(256)]get{var sb=new List<byte>();byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}}public char Char{[凾(256)]get{byte b;do b=Read();while(b<=' ');return(char)b;}}[凾(256)]public static implicit operator int(_R cr)=>cr.Int;[凾(256)]public static implicit operator uint(_R cr)=>cr.UInt;[凾(256)]public static implicit operator long(_R cr)=>cr.Long;[凾(256)]public static implicit operator ulong(_R cr)=>cr.ULong;[凾(256)]public static implicit operator double(_R cr)=>cr.Double;[凾(256)]public static implicit operator decimal(_R cr)=>cr.Decimal;[凾(256)]public static implicit operator string(_R cr)=>cr.Ascii;}}
namespace Kzrnm.Competitive.IO{using _R=PropertyRepeatReader;public struct PropertyRepeatReader{internal readonly PropertyConsoleReader cr;internal readonly int count;[凾(256)]internal PropertyRepeatReader(PropertyConsoleReader cr,int count){this.cr=cr;this.count=count;}public string[]Line{[凾(256)]get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.Line;return arr;}}public string[]String{[凾(256)]get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.String;return arr;}}public string[]Ascii{[凾(256)]get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.Ascii;return arr;}}public int[]Int{[凾(256)]get{var arr=new int[count];for(var i=0;i<count;i++)arr[i]=cr.Int;return arr;}}public int[]Int0{[凾(256)]get{var arr=new int[count];for(var i=0;i<count;i++)arr[i]=cr.Int0;return arr;}}public uint[]UInt{[凾(256)]get{var arr=new uint[count];for(var i=0;i<count;i++)arr[i]=cr.UInt;return arr;}}public uint[]UInt0{[凾(256)]get{var arr=new uint[count];for(var i=0;i<count;i++)arr[i]=cr.UInt0;return arr;}}public long[]Long{[凾(256)]get{var arr=new long[count];for(var i=0;i<count;i++)arr[i]=cr.Long;return arr;}}public long[]Long0{[凾(256)]get{var arr=new long[count];for(var i=0;i<count;i++)arr[i]=cr.Long0;return arr;}}public ulong[]ULong{[凾(256)]get{var arr=new ulong[count];for(var i=0;i<count;i++)arr[i]=cr.ULong;return arr;}}public ulong[]ULong0{[凾(256)]get{var arr=new ulong[count];for(var i=0;i<count;i++)arr[i]=cr.ULong0;return arr;}}public double[]Double{[凾(256)]get{var arr=new double[count];for(var i=0;i<count;i++)arr[i]=cr.Double;return arr;}}public decimal[]Decimal{[凾(256)]get{var arr=new decimal[count];for(var i=0;i<count;i++)arr[i]=cr.Decimal;return arr;}}[凾(256)]public static implicit operator string[](_R rr)=>rr.Ascii;[凾(256)]public static implicit operator int[](_R rr)=>rr.Int;[凾(256)]public static implicit operator uint[](_R rr)=>rr.UInt;[凾(256)]public static implicit operator long[](_R rr)=>rr.Long;[凾(256)]public static implicit operator ulong[](_R rr)=>rr.ULong;[凾(256)]public static implicit operator double[](_R rr)=>rr.Double;[凾(256)]public static implicit operator decimal[](_R rr)=>rr.Decimal;}public static class PRepeatEx{[凾(256)]public static _R Repeat(this PropertyConsoleReader cr,int count)=>new _R(cr,count);}}
namespace Kzrnm.Competitive.IO{public static class PropertyRepeatReaderSelect{[凾(256)]public static T[]Select<T>(this PropertyRepeatReader r,Func<PropertyConsoleReader,T>factory){var c=r.count;var arr=new T[c];for(var i=0;i<c;i++)arr[i]=factory(r.cr);return arr;}[凾(256)]public static T[]Select<T>(this PropertyRepeatReader r,Func<PropertyConsoleReader,int,T>factory){var c=r.count;var arr=new T[c];for(var i=0;i<c;i++)arr[i]=factory(r.cr,i);return arr;}}}
namespace Kzrnm.Competitive.IO{using static Utf8Formatter;using _W=Utf8ConsoleWriter;public sealed class Utf8ConsoleWriter:IDisposable{internal static readonly UTF8Encoding Utf8NoBom=new UTF8Encoding(false);internal const int BufSize=1<<12;internal readonly Stream output;internal byte[]buf;internal int len;public Utf8ConsoleWriter():this(Console.OpenStandardOutput()){}public Utf8ConsoleWriter(Stream output):this(output,BufSize){}public Utf8ConsoleWriter(Stream output,int bufferSize){this.output=output;buf=new byte[bufferSize];}public StreamWriter ToStreamWriter(){Flush();return new StreamWriter(output,Utf8NoBom);}[凾(256)]public void Flush(){output.Write(buf,0,len);len=0;}void IDisposable.Dispose()=>Flush();[凾(256)]private Span<byte>EnsureBuf(int size){if(buf.Length-len<size){Flush();}return buf.AsSpan(len,size);}[凾(256|512)]public _W Write<T>(T v){void FormatFloat(double d,out int b)=>TryFormat(d,EnsureBuf(Math.Max(25+(int)Math.Log10(Math.Abs(d)),32)),out b,new StandardFormat('F',20));void FormatDec(decimal d,out int b)=>TryFormat(d,EnsureBuf(Math.Max(25+(int)Math.Log10((double)Math.Abs(d)),32)),out b,new StandardFormat('F',20));int bw;if(typeof(T)==typeof(int))TryFormat((int)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(long))TryFormat((long)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(uint))TryFormat((uint)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(ulong))TryFormat((ulong)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(short))TryFormat((short)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(ushort))TryFormat((ushort)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(byte))TryFormat((byte)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(sbyte))TryFormat((sbyte)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(float))FormatFloat((float)(object)v,out bw);else if(typeof(T)==typeof(double))FormatFloat((double)(object)v,out bw);else if(typeof(T)==typeof(decimal))FormatDec((decimal)(object)v,out bw);else if(typeof(T)==typeof(char)){var dst=EnsureBuf(6);var c=(char)(object)v;if(c<0x007f){dst[0]=(byte)c;bw=1;}else{Span<char>s=stackalloc char[1]{c};bw=Utf8NoBom.GetBytes(s,dst);}}else if(v is char[]charr)return Write(charr.AsSpan());else if(v is IUtf8ConsoleWriterFormatter f){f.Write(this);return this;}else return Write(v.ToString().AsSpan());len+=bw;return this;}[凾(256|512)]public _W Write(ReadOnlySpan<char>v){var mlen=Utf8NoBom.GetMaxByteCount(v.Length);if(mlen>buf.Length){Flush();buf=new byte[mlen*2];}else if(mlen>buf.Length-len){Flush();}var bw=Utf8NoBom.GetBytes(v,buf.AsSpan(len));len+=bw;return this;}[凾(256)]public _W WriteLine()=>Write('\n');[凾(256)]public _W WriteLine<T>(T v){Write(v);return Write('\n');}[凾(256)]public _W WriteLine(ReadOnlySpan<char>v){Write(v);return Write('\n');}[凾(256)]public _W WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);[凾(256)]public _W WriteLineJoin<T1,T2>((T1,T2)tuple){Write(tuple.Item1);Write(' ');return WriteLine(tuple.Item2);}[凾(256)]public _W WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');return WriteLine(tuple.Item3);}[凾(256)]public _W WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');Write(tuple.Item3);Write(' ');return WriteLine(tuple.Item4);}[凾(256)]public _W WriteLineJoin<TTuple>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++){if(i!=0)Write(' ');Write(tuple[i]);}return WriteLine();}[凾(256)]public _W WriteLineJoin(params object[]col)=>WriteMany(' ',col);[凾(256)]public _W WriteLineJoin<T1,T2>(T1 v1,T2 v2){Write(v1);Write(' ');return WriteLine(v2);}[凾(256)]public _W WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){Write(v1);Write(' ');Write(v2);Write(' ');return WriteLine(v3);}[凾(256)]public _W WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){Write(v1);Write(' ');Write(v2);Write(' ');Write(v3);Write(' ');return WriteLine(v4);}[凾(256)]public _W WriteLineJoin<T>(params T[]col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);[凾(256)]public _W WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);[凾(256)]public _W WriteLines<T>(T[]col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);[凾(256)]public _W WriteGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}[凾(256)]public _W WriteGrid<TTuple>(IEnumerable<TTuple>tuples)where TTuple:ITuple{foreach(var tup in tuples)WriteLineJoin(tup);return this;}[凾(256)]private _W WriteMany<T>(char sep,IEnumerable<T>col){if(col is T[]array)return WriteMany(sep,(ReadOnlySpan<T>)array);var en=col.GetEnumerator();if(en.MoveNext()){Write(en.Current);while(en.MoveNext()){Write(sep);Write(en.Current);}}return WriteLine();}[凾(256)]private _W WriteMany<T>(char sep,ReadOnlySpan<T>col){if(col.Length>0){Write(col[0]);foreach(var c in col.Slice(1)){Write(sep);Write(c);}}return WriteLine();}}public interface IUtf8ConsoleWriterFormatter{void Write(_W cw);}}
namespace Kzrnm.Competitive{using O=ConsoleOutput;public static class ConsoleOutputExt{public static O ToConsoleOutput<T>(this T f)where T:IUtf8ConsoleWriterFormatter{var cw=O.cw;f.Write(cw);return cw.WriteLine();}}public struct ConsoleOutput{public static Utf8ConsoleWriter cw;public static implicit operator O(int v)=>cw.WriteLine(v);public static implicit operator O(long v)=>cw.WriteLine(v);public static implicit operator O(uint v)=>cw.WriteLine(v);public static implicit operator O(ulong v)=>cw.WriteLine(v);public static implicit operator O(double v)=>cw.WriteLine(v);public static implicit operator O(decimal v)=>cw.WriteLine(v);public static implicit operator O(char v)=>cw.WriteLine(v);public static implicit operator O(char[]v)=>cw.WriteLine((ReadOnlySpan<char>)v);public static implicit operator O(string v)=>cw.WriteLine((ReadOnlySpan<char>)v);public static implicit operator O(bool v)=>cw.WriteLine((ReadOnlySpan<char>)(v?"Yes":"No"));public static implicit operator O(Utf8ConsoleWriter _)=>default;}}
internal partial class Program{public PropertyConsoleReader cr;public Utf8ConsoleWriter cw;public Program(PropertyConsoleReader r,Utf8ConsoleWriter w){cr=r;ConsoleOutput.cw=cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){int Q=__ManyTestCases?cr.Int:1;while( --Q>=0)Calc();cw.Flush();}}
namespace Kzrnm.Competitive{public static class __ArrayExtension{[凾(256)]public static T[]Fill<T>(this T[]arr,T value){arr.AsSpan().Fill(value);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr){Array.Sort(arr);return arr;}[凾(256)]public static string[]Sort(this string[]arr)=>Sort(arr,StringComparer.Ordinal);[凾(256)]public static T[]Sort<T,U>(this T[]arr,Func<T,U>selector)where U:IComparable<U>{Array.Sort(arr.Select(selector).ToArray(),arr);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr,Comparison<T>comparison){Array.Sort(arr,comparison);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr,IComparer<T>comparer){Array.Sort(arr,comparer);return arr;}[凾(256)]public static T[]Reverse<T>(this T[]arr){Array.Reverse(arr);return arr;}[凾(256)]public static ref T Get<T>(this T[]arr,int index){if(index<0)index+=arr.Length;return ref arr[index];}[凾(256)]public static ref readonly T GetOrDummy<T>(this ReadOnlySpan<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this Span<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this T[]arr,int index,T dummy=default)=>ref GetOrDummy(arr.AsSpan(),index,dummy);[凾(256)]public static ref T GetOrDummy<T>(this T[][]arr,int index1,int index2,T dummy=default){if((uint)index1<(uint)arr.Length)return ref GetOrDummy(arr[index1],index2,dummy);Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this T[][][]arr,int index1,int index2,int index3,T dummy=default){if((uint)index1<(uint)arr.Length)return ref GetOrDummy(arr[index1],index2,index3,dummy);Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}private static class Dummy<T>{public static T dummy;}[凾(256)]public static int FindByBinarySearch<T,TCv>(this T[]arr,TCv value)where TCv:IComparable<T> =>FindByBinarySearch((ReadOnlySpan<T>)arr,value);[凾(256)]public static int FindByBinarySearch<T,TCv>(this Span<T>arr,TCv value)where TCv:IComparable<T> =>FindByBinarySearch((ReadOnlySpan<T>)arr,value);[凾(256)]public static int FindByBinarySearch<T,TCv>(this ReadOnlySpan<T>arr,TCv value)where TCv:IComparable<T>{int ix=arr.BinarySearch(value);if(ix<0)ix=~ix;return ix;}}}
namespace Kzrnm.Competitive{public static class ConvolutionAnyMod{[凾(256)]public static uint[]Convolution(ReadOnlySpan<int>a,ReadOnlySpan<int>b,int mod)=>Convolution(MemoryMarshal.Cast<int,uint>(a),MemoryMarshal.Cast<int,uint>(b),mod);[凾(256)]public static uint[]Convolution(ReadOnlySpan<uint>a,ReadOnlySpan<uint>b,int mod){uint umod=(uint)mod;unchecked{var n=a.Length;var m=b.Length;var la=new long[n];for(int i=0;i<la.Length;i++)la[i]=a[i]%umod;var lb=new long[m];for(int i=0;i<lb.Length;i++)lb[i]=b[i]%umod;if(n==0||m==0){return Array.Empty<uint>();}const long Mod1=167772161;const long Mod2=469762049;const long Mod3=754974721;const long M1i2=104391568;const long M12i3=190329765;long M12i=(long)(ulong)(Mod1*Mod2)%umod;var c1=MathLib.Convolution<FFTMod1>(la,lb);var c2=MathLib.Convolution<FFTMod2>(la,lb);var c3=MathLib.Convolution<FFTMod3>(la,lb);var c=new uint[n+m-1];for(int i=0;i<c.Length;i++){var v1=((c2[i]-c1[i])*M1i2)%Mod2;if(v1<0)v1+=Mod2;var v2=(c3[i]-(c1[i]+Mod1*v1)%Mod3)*M12i3%Mod3;if(v2<0)v2+=Mod3;var x=(c1[i]+Mod1*v1+M12i*v2)%mod;if(x<0)x+=mod;c[i]=(uint)x;}return c;}}[凾(256)]public static uint[]Convolution<TMod>(ReadOnlySpan<int>a,ReadOnlySpan<int>b)where TMod:struct,IStaticMod=>Convolution<TMod>(MemoryMarshal.Cast<int,uint>(a),MemoryMarshal.Cast<int,uint>(b));[凾(256)]public static StaticModInt<TMod>[]Convolution<TMod>(StaticModInt<TMod>[]a,StaticModInt<TMod>[]b)where TMod:struct,IStaticMod=>Convolution((ReadOnlySpan<StaticModInt<TMod>>)a,b);[凾(256)]public static StaticModInt<TMod>[]Convolution<TMod>(Span<StaticModInt<TMod>>a,Span<StaticModInt<TMod>>b)where TMod:struct,IStaticMod=>Convolution((ReadOnlySpan<StaticModInt<TMod>>)a,b);[凾(256)]public static StaticModInt<TMod>[]Convolution<TMod>(ReadOnlySpan<StaticModInt<TMod>>a,ReadOnlySpan<StaticModInt<TMod>>b)where TMod:struct,IStaticMod{var mod=new TMod().Mod;if(new TMod().IsPrime&&a.Length+b.Length-1<=(1<<InternalBit.BSF(mod-1))){return MathLib.Convolution(a,b);}return MemoryMarshal.Cast<uint,StaticModInt<TMod>>(ConvolutionImpl<TMod>(MemoryMarshal.Cast<StaticModInt<TMod>,uint>(a),MemoryMarshal.Cast<StaticModInt<TMod>,uint>(b))).ToArray();}[凾(256)]public static uint[]Convolution<TMod>(ReadOnlySpan<uint>a,ReadOnlySpan<uint>b)where TMod:struct,IStaticMod{if(new TMod().IsPrime&&a.Length+b.Length-1<=(1<<InternalBit.BSF(new TMod().Mod-1))){return MathLib.Convolution<TMod>(a,b);}return ConvolutionImpl<TMod>(a,b);}[凾(256)]private static uint[]ConvolutionImpl<TMod>(ReadOnlySpan<uint>a,ReadOnlySpan<uint>b)where TMod:struct,IStaticMod{var op=new TMod();unchecked{var n=a.Length;var m=b.Length;var la=new long[n];for(int i=0;i<la.Length;i++)la[i]=a[i]%op.Mod;var lb=new long[m];for(int i=0;i<lb.Length;i++)lb[i]=b[i]%op.Mod;if(n==0||m==0){return Array.Empty<uint>();}const long Mod1=167772161;const long Mod2=469762049;const long Mod3=754974721;const long M1i2=104391568;const long M12i3=190329765;long M12i=(long)(ulong)(Mod1*Mod2)%op.Mod;var c1=MathLib.Convolution<FFTMod1>(la,lb);var c2=MathLib.Convolution<FFTMod2>(la,lb);var c3=MathLib.Convolution<FFTMod3>(la,lb);var c=new uint[n+m-1];for(int i=0;i<c.Length;i++){var v1=((c2[i]-c1[i])*M1i2)%Mod2;if(v1<0)v1+=Mod2;var v2=(c3[i]-(c1[i]+Mod1*v1)%Mod3)*M12i3%Mod3;if(v2<0)v2+=Mod3;var x=(c1[i]+Mod1*v1+M12i*v2)%op.Mod;if(x<0)x+=op.Mod;c[i]=(uint)x;}return c;}}[凾(256)]internal static bool CanNtt<TMod>()where TMod:struct,IStaticMod{var m=new TMod();return m.IsPrime&&BitOperations.TrailingZeroCount(m.Mod-1)>=23;}private readonly struct FFTMod1:IStaticMod{public uint Mod=>167772161;public bool IsPrime=>true;}private readonly struct FFTMod2:IStaticMod{public uint Mod=>469762049;public bool IsPrime=>true;}private readonly struct FFTMod3:IStaticMod{public uint Mod=>754974721;public bool IsPrime=>true;}}}
namespace Kzrnm.Competitive{public static partial class NumberTheoreticTransform<T>where T:struct,IStaticMod{internal static readonly StaticModInt<T>pr=BuildPr();static StaticModInt<T>BuildPr(){var op=new T();if(op.Mod==2)return 1;var ds=new ulong[32];int idx=0;uint m=op.Mod-1;for(uint i=2;(ulong)i*i<=m;++i){if(m%i==0){ds[idx++]=i;while(m%i==0)m/=i;}}if(m!=1)ds[idx++]=m;uint pr=2;while(true){for(int i=0;i<idx;++i){ulong a=pr,r=1;uint b=(uint)((op.Mod-1)/ds[i]);while(b!=0){if((b&1)!=0)r=r*a%op.Mod;a=a*a%op.Mod;b>>=1;}if(r==1)goto NEXT;}return pr;NEXT:++pr;}}static StaticModInt<T>[]dws,dys;static readonly MontgomeryModInt<T>[]dw,dy;[凾(256)]internal static bool CanNtt(){var m=new T();return m.IsPrime&&BitOperations.TrailingZeroCount(m.Mod-1)>=23;}static NumberTheoreticTransform(){if(!CanNtt())return;var level=BitOperations.TrailingZeroCount(new T().Mod-1);dws=new StaticModInt<T>[level];dys=new StaticModInt<T>[level];SetWy(level);dw=new MontgomeryModInt<T>[level];dy=new MontgomeryModInt<T>[level];for(int i=0;i<dw.Length;i++)dw[i]=dws[i].Value;for(int i=0;i<dy.Length;i++)dy[i]=dys[i].Value;}static void SetWy(int k){var w=new StaticModInt<T>[k];var y=new StaticModInt<T>[k];w[k-1]=pr.Pow((new T().Mod-1)/(1u<<k));y[k-1]=w[k-1].Inv();for(int i=k-2;i>0;--i){w[i]=w[i+1]*w[i+1];y[i]=y[i+1]*y[i+1];}dws[0]=dys[0]=w[1]*w[1];dws[1]=w[1];dys[1]=y[1];dws[2]=w[2];dys[2]=y[2];for(int i=3;i<y.Length;++i){dws[i]=dws[i-1]*y[i-2]*w[i];dys[i]=dys[i-1]*w[i-2]*y[i];}}static StaticModInt<T>[]MultiplyNative(ReadOnlySpan<StaticModInt<T>>a,ReadOnlySpan<StaticModInt<T>>b){if(a.Length==0||b.Length==0)return Array.Empty<StaticModInt<T>>();int l=a.Length+b.Length-1;var s=new StaticModInt<T>[l];for(int i=0;i<a.Length;++i)for(int j=0;j<b.Length;++j)s[i+j]+=a[i]*b[j];return s;}[凾(256)]public static void Ntt(Span<StaticModInt<T>>a){if(Avx2.IsSupported)NttSimd(a);else NttLogical(a);}[凾(256)]public static void INtt(Span<StaticModInt<T>>a){if(Avx2.IsSupported)INttSimd(a);else INttLogical(a);}[凾(256)]public static StaticModInt<T>[]Multiply(ReadOnlySpan<uint>a,ReadOnlySpan<uint>b)=>Multiply(MemoryMarshal.Cast<uint,StaticModInt<T>>(a),MemoryMarshal.Cast<uint,StaticModInt<T>>(b));[凾(256)]public static StaticModInt<T>[]Multiply(ReadOnlySpan<StaticModInt<T>>a,ReadOnlySpan<StaticModInt<T>>b)=>Avx2.IsSupported?MultiplySimd(a,b):MultiplyLogical(a,b);[凾(256)]public static StaticModInt<T>[]NttDoubling(ReadOnlySpan<StaticModInt<T>>a){var res=new StaticModInt<T>[2*a.Length];a.CopyTo(res);var b=res.AsSpan(a.Length);a.CopyTo(b);INtt(b);var r=StaticModInt<T>.Raw(1);var zeta=pr.Pow((new T().Mod-1)/((uint)a.Length<<1));for(int i=0;i<b.Length;i++){b[i]*=r;r*=zeta;}Ntt(b);return res;}}}
namespace Kzrnm.Competitive{using static BitOperations;public static partial class NumberTheoreticTransform<T>where T:struct,IStaticMod{[凾(512)]static void Fft4(Span<StaticModInt<T>>a,int k){if(a.Length<=1)return;if(k==1){var a1=a[1];a[1]=a[0]-a[1];a[0]=a[0]+a1;return;}if((k&1)!=0){int vv=1<<(k-1);for(int j=0;j<vv;++j){var ajv=a[j+vv];a[j+vv]=a[j]-ajv;a[j]+=ajv;}}int u=1<<(2+(k&1));int v=1<<(k-2-(k&1));var one=StaticModInt<T>.Raw(1);var imag=dws[1];while(v!=0){{int j0=0;int j1=v;int j2=j1+v;int j3=j2+v;for(;j0<v;++j0, ++j1, ++j2, ++j3){StaticModInt<T>t0=a[j0],t1=a[j1],t2=a[j2],t3=a[j3];StaticModInt<T>t0p2=t0+t2,t1p3=t1+t3;StaticModInt<T>t0m2=t0-t2,t1m3=(t1-t3)*imag;a[j0]=t0p2+t1p3;a[j1]=t0p2-t1p3;a[j2]=t0m2+t1m3;a[j3]=t0m2-t1m3;}}var xx=one*dws[2];for(int jh=4;jh<u;){var ww=xx*xx;var wx=ww*xx;int j0=jh*v;int je=j0+v;int j2=je+v;for(;j0<je;++j0, ++j2){StaticModInt<T>t0=a[j0],t1=a[j0+v]*xx,t2=a[j2]*ww,t3=a[j2+v]*wx;StaticModInt<T>t0p2=t0+t2,t1p3=t1+t3;StaticModInt<T>t0m2=t0-t2,t1m3=(t1-t3)*imag;a[j0]=t0p2+t1p3;a[j0+v]=t0p2-t1p3;a[j2]=t0m2+t1m3;a[j2+v]=t0m2-t1m3;}xx*=dws[TrailingZeroCount(jh+=4)];}u<<=2;v>>=2;}}[凾(512)]static void IFft4(Span<StaticModInt<T>>a,int k){if(a.Length<=1)return;if(k==1){var a1=a[1];a[1]=a[0]-a[1];a[0]=a[0]+a1;return;}int u=1<<(k-2);int v=1;var one=StaticModInt<T>.Raw(1);var imag=dys[1];while(u!=0){{int j0=0;int j1=v;int j2=v+v;int j3=j2+v;for(;j0<v;++j0, ++j1, ++j2, ++j3){StaticModInt<T>t0=a[j0],t1=a[j1],t2=a[j2],t3=a[j3];StaticModInt<T>t0p1=t0+t1,t2p3=t2+t3;StaticModInt<T>t0m1=t0-t1,t2m3=(t2-t3)*imag;a[j0]=t0p1+t2p3;a[j2]=t0p1-t2p3;a[j1]=t0m1+t2m3;a[j3]=t0m1-t2m3;}}var xx=one*dys[2];u<<=2;for(int jh=4;jh<u;){var ww=xx*xx;var yy=xx*imag;int j0=jh*v;int je=j0+v;int j2=je+v;for(;j0<je;++j0, ++j2){StaticModInt<T>t0=a[j0],t1=a[j0+v],t2=a[j2],t3=a[j2+v];StaticModInt<T>t0p1=t0+t1,t2p3=t2+t3;StaticModInt<T>t0m1=(t0-t1)*xx,t2m3=(t2-t3)*yy;a[j0]=t0p1+t2p3;a[j2]=(t0p1-t2p3)*ww;a[j0+v]=t0m1+t2m3;a[j2+v]=(t0m1-t2m3)*ww;}xx*=dys[TrailingZeroCount(jh+=4)];}u>>=4;v<<=2;}if((k&1)!=0){u=1<<(k-1);for(int j=0;j<u;++j){StaticModInt<T>ajv=a[j]-a[j+u];a[j]+=a[j+u];a[j+u]=ajv;}}}[凾(256)]internal static void NttLogical(Span<StaticModInt<T>>a){if(a.Length<=1)return;Fft4(a,TrailingZeroCount(a.Length));}[凾(256)]internal static void INttLogical(Span<StaticModInt<T>>a){if(a.Length<=1)return;IFft4(a,TrailingZeroCount(a.Length));var iv=new StaticModInt<T>(a.Length).Inv();for(int i=0;i<a.Length;i++)a[i]*=iv;}[凾(512)]internal static StaticModInt<T>[]MultiplyLogical(ReadOnlySpan<StaticModInt<T>>a,ReadOnlySpan<StaticModInt<T>>b){if(Math.Min(a.Length,b.Length)<=60)return MultiplyNative(a,b);int l=a.Length+b.Length-1;var k=InternalBit.CeilPow2(l);var M=1<<k;SetWy(k);var s=new StaticModInt<T>[M];var t=new StaticModInt<T>[M];a.CopyTo(s);b.CopyTo(t);Fft4(s,k);Fft4(t,k);for(int i=0;i<s.Length;++i)s[i]*=t[i];IFft4(s,k);var invm=new StaticModInt<T>(M).Inv();var res=new StaticModInt<T>[l];for(int i=0;i<res.Length;++i)res[i]=s[i]*invm;return res;}}}
namespace Kzrnm.Competitive{using static BitOperations;using static SimdMontgomery;public static partial class NumberTheoreticTransform<T>where T:struct,IStaticMod{[凾(256)]static ref Vector128<uint>ToVector128(ref MontgomeryModInt<T>m)=>ref Unsafe.As<MontgomeryModInt<T>,Vector128<uint>>(ref m);[凾(256)]static ref Vector256<uint>ToVector256(ref MontgomeryModInt<T>m)=>ref Unsafe.As<MontgomeryModInt<T>,Vector256<uint>>(ref m);[凾(256)]static void NttSimd(Span<StaticModInt<T>>a){var b=new MontgomeryModInt<T>[a.Length];for(int i=0;i<a.Length;i++)b[i]=a[i].Value;NttSimd(b);for(int i=0;i<a.Length;i++)a[i]=StaticModInt<T>.Raw(b[i].Value);}[凾(256)]static void NttSimd(Span<MontgomeryModInt<T>>a){int k=TrailingZeroCount(a.Length)&31;if(k==0)return;if(k==1){var a1=a[1];a[1]=a[0]-a[1];a[0]=a[0]+a1;return;}if((k&1)!=0){int vv=1<<(k-1);if(vv<8){for(int j=0;j<vv;++j){var ajv=a[j+vv];a[j+vv]=a[j]-ajv;a[j]+=ajv;}}else{var m0=Vector256<uint>.Zero;var m2=Vector256.Create(new T().Mod*2);for(int j0=0,j1=vv;j0<vv;j0+=8,j1+=8){ref var T0=ref ToVector256(ref a[j0]);ref var T1=ref ToVector256(ref a[j1]);var naj=MontgomeryAdd(T0,T1,m2,m0);var najv=MontgomerySubtract(T0,T1,m2,m0);T0=naj;T1=najv;}}}int u=1<<(2+(k&1));int v=1<<(k-2-(k&1));MontgomeryModInt<T>one=1;var imag=dw[1];while(v!=0){if(v==1){var xx=one;for(int jh=0;jh<u;){var ww=xx*xx;var wx=ww*xx;var t0=a[jh+0];var t1=a[jh+1]*xx;var t2=a[jh+2]*ww;var t3=a[jh+3]*wx;var t0p2=t0+t2;var t1p3=t1+t3;var t0m2=t0-t2;var t1m3=(t1-t3)*imag;a[jh+0]=t0p2+t1p3;a[jh+1]=t0p2-t1p3;a[jh+2]=t0m2+t1m3;a[jh+3]=t0m2-t1m3;xx*=dw[TrailingZeroCount(jh+=4)];}}else if(v==4){var m0=Vector128<uint>.Zero;var m1=Vector128.Create(new T().Mod);var m2=Vector128.Create(new T().Mod*2);var r=Vector128.Create(MontgomeryModInt<T>.r);var Imag=Vector128.Create(imag._v);var xx=one;for(int jh=0;jh<u;){if(jh==0){int j0=0;int j1=v;int j2=j1+v;int j3=j2+v;int je=v;for(;j0<je;j0+=4,j1+=4,j2+=4,j3+=4){ref var T0=ref ToVector128(ref a[j0]);ref var T1=ref ToVector128(ref a[j1]);ref var T2=ref ToVector128(ref a[j2]);ref var T3=ref ToVector128(ref a[j3]);var T0P2=MontgomeryAdd(T0,T2,m2,m0);var T1P3=MontgomeryAdd(T1,T3,m2,m0);var T0M2=MontgomerySubtract(T0,T2,m2,m0);var T1M3=MontgomeryMultiply(MontgomerySubtract(T1,T3,m2,m0),Imag,r,m1);T0=MontgomeryAdd(T0P2,T1P3,m2,m0);T1=MontgomerySubtract(T0P2,T1P3,m2,m0);T2=MontgomeryAdd(T0M2,T1M3,m2,m0);T3=MontgomerySubtract(T0M2,T1M3,m2,m0);}}else{var ww=xx*xx;var wx=ww*xx;var WW=Vector128.Create(ww._v);var WX=Vector128.Create(wx._v);var XX=Vector128.Create(xx._v);int j0=jh*v;int j1=j0+v;int j2=j1+v;int j3=j2+v;int je=j1;for(;j0<je;j0+=4,j1+=4,j2+=4,j3+=4){ref var T0=ref ToVector128(ref a[j0]);ref var T1=ref ToVector128(ref a[j1]);ref var T2=ref ToVector128(ref a[j2]);ref var T3=ref ToVector128(ref a[j3]);var MT1=MontgomeryMultiply(T1,XX,r,m1);var MT2=MontgomeryMultiply(T2,WW,r,m1);var MT3=MontgomeryMultiply(T3,WX,r,m1);var T0P2=MontgomeryAdd(T0,MT2,m2,m0);var T1P3=MontgomeryAdd(MT1,MT3,m2,m0);var T0M2=MontgomerySubtract(T0,MT2,m2,m0);var T1M3=MontgomeryMultiply(MontgomerySubtract(MT1,MT3,m2,m0),Imag,r,m1);T0=MontgomeryAdd(T0P2,T1P3,m2,m0);T1=MontgomerySubtract(T0P2,T1P3,m2,m0);T2=MontgomeryAdd(T0M2,T1M3,m2,m0);T3=MontgomerySubtract(T0M2,T1M3,m2,m0);}}xx*=dw[TrailingZeroCount(jh+=4)];}}else{var m0=Vector256<uint>.Zero;var m1=Vector256.Create(new T().Mod);var m2=Vector256.Create(new T().Mod*2);var r=Vector256.Create(MontgomeryModInt<T>.r);var Imag=Vector256.Create(imag._v);var xx=one;for(int jh=0;jh<u;){if(jh==0){int j0=0;int j1=v;int j2=j1+v;int j3=j2+v;int je=v;for(;j0<je;j0+=8,j1+=8,j2+=8,j3+=8){ref var T0=ref ToVector256(ref a[j0]);ref var T1=ref ToVector256(ref a[j1]);ref var T2=ref ToVector256(ref a[j2]);ref var T3=ref ToVector256(ref a[j3]);var T0P2=MontgomeryAdd(T0,T2,m2,m0);var T1P3=MontgomeryAdd(T1,T3,m2,m0);var T0M2=MontgomerySubtract(T0,T2,m2,m0);var T1M3=MontgomeryMultiply(MontgomerySubtract(T1,T3,m2,m0),Imag,r,m1);T0=MontgomeryAdd(T0P2,T1P3,m2,m0);T1=MontgomerySubtract(T0P2,T1P3,m2,m0);T2=MontgomeryAdd(T0M2,T1M3,m2,m0);T3=MontgomerySubtract(T0M2,T1M3,m2,m0);}}else{var ww=xx*xx;var wx=ww*xx;var WW=Vector256.Create(ww._v);var WX=Vector256.Create(wx._v);var XX=Vector256.Create(xx._v);int j0=jh*v;int j1=j0+v;int j2=j1+v;int j3=j2+v;int je=j1;for(;j0<je;j0+=8,j1+=8,j2+=8,j3+=8){ref var T0=ref ToVector256(ref a[j0]);ref var T1=ref ToVector256(ref a[j1]);ref var T2=ref ToVector256(ref a[j2]);ref var T3=ref ToVector256(ref a[j3]);var MT1=MontgomeryMultiply(T1,XX,r,m1);var MT2=MontgomeryMultiply(T2,WW,r,m1);var MT3=MontgomeryMultiply(T3,WX,r,m1);var T0P2=MontgomeryAdd(T0,MT2,m2,m0);var T1P3=MontgomeryAdd(MT1,MT3,m2,m0);var T0M2=MontgomerySubtract(T0,MT2,m2,m0);var T1M3=MontgomeryMultiply(MontgomerySubtract(MT1,MT3,m2,m0),Imag,r,m1);T0=MontgomeryAdd(T0P2,T1P3,m2,m0);T1=MontgomerySubtract(T0P2,T1P3,m2,m0);T2=MontgomeryAdd(T0M2,T1M3,m2,m0);T3=MontgomerySubtract(T0M2,T1M3,m2,m0);}}xx*=dw[TrailingZeroCount(jh+=4)];}}u<<=2;v>>=2;}}[凾(256)]static void INttSimd(Span<StaticModInt<T>>a){var b=new MontgomeryModInt<T>[a.Length];for(int i=0;i<a.Length;i++)b[i]=a[i].Value;INttSimd(b,true);for(int i=0;i<a.Length;i++)a[i]=StaticModInt<T>.Raw(b[i].Value);}[凾(256)]static void INttSimd(Span<MontgomeryModInt<T>>a,bool normalize){int k=TrailingZeroCount(a.Length)&31;if(k==0)return;if(k==1){var a1=a[1];a[1]=a[0]-a[1];a[0]=a[0]+a1;if(normalize){var iv2=new MontgomeryModInt<T>(2).Inv();a[0]*=iv2;a[1]*=iv2;}return;}int u=1<<(k-2);int v=1;MontgomeryModInt<T>one=1,imag=dy[1];while(u!=0){if(v==1){var xx=one;u<<=2;for(int jh=0;jh<u;){var ww=xx*xx;var yy=xx*imag;var t0=a[jh+0];var t1=a[jh+1];var t2=a[jh+2];var t3=a[jh+3];var t0p1=t0+t1;var t2p3=t2+t3;var t0m1=(t0-t1)*xx;var t2m3=(t2-t3)*yy;a[jh+0]=t0p1+t2p3;a[jh+2]=(t0p1-t2p3)*ww;a[jh+1]=t0m1+t2m3;a[jh+3]=(t0m1-t2m3)*ww;xx*=dy[TrailingZeroCount(jh+=4)];}}else if(v==4){var m0=Vector128<uint>.Zero;var m1=Vector128.Create(new T().Mod);var m2=Vector128.Create(new T().Mod*2);var r=Vector128.Create(MontgomeryModInt<T>.r);var Imag=Vector128.Create(imag._v);var xx=one;u<<=2;for(int jh=0;jh<u;){if(jh==0){int j0=0;int j1=v;int j2=v+v;int j3=j2+v;for(;j0<v;j0+=4,j1+=4,j2+=4,j3+=4){ref var T0=ref ToVector128(ref a[j0]);ref var T1=ref ToVector128(ref a[j1]);ref var T2=ref ToVector128(ref a[j2]);ref var T3=ref ToVector128(ref a[j3]);var T0P1=MontgomeryAdd(T0,T1,m2,m0);var T2P3=MontgomeryAdd(T2,T3,m2,m0);var T0M1=MontgomerySubtract(T0,T1,m2,m0);var T2M3=MontgomeryMultiply(MontgomerySubtract(T2,T3,m2,m0),Imag,r,m1);T0=MontgomeryAdd(T0P1,T2P3,m2,m0);T2=MontgomerySubtract(T0P1,T2P3,m2,m0);T1=MontgomeryAdd(T0M1,T2M3,m2,m0);T3=MontgomerySubtract(T0M1,T2M3,m2,m0);}}else{var ww=xx*xx;var yy=xx*imag;var WW=Vector128.Create(ww._v);var XX=Vector128.Create(xx._v);var YY=Vector128.Create(yy._v);int j0=jh*v;int j1=j0+v;int j2=j1+v;int j3=j2+v;int je=j1;for(;j0<je;j0+=4,j1+=4,j2+=4,j3+=4){ref var T0=ref ToVector128(ref a[j0]);ref var T1=ref ToVector128(ref a[j1]);ref var T2=ref ToVector128(ref a[j2]);ref var T3=ref ToVector128(ref a[j3]);var T0P1=MontgomeryAdd(T0,T1,m2,m0);var T2P3=MontgomeryAdd(T2,T3,m2,m0);var T0M1=MontgomeryMultiply(MontgomerySubtract(T0,T1,m2,m0),XX,r,m1);var T2M3=MontgomeryMultiply(MontgomerySubtract(T2,T3,m2,m0),YY,r,m1);T0=MontgomeryAdd(T0P1,T2P3,m2,m0);T2=MontgomeryMultiply(MontgomerySubtract(T0P1,T2P3,m2,m0),WW,r,m1);T1=MontgomeryAdd(T0M1,T2M3,m2,m0);T3=MontgomeryMultiply(MontgomerySubtract(T0M1,T2M3,m2,m0),WW,r,m1);}}xx*=dy[TrailingZeroCount(jh+=4)];}}else{var m0=Vector256<uint>.Zero;var m1=Vector256.Create(new T().Mod);var m2=Vector256.Create(new T().Mod*2);var r=Vector256.Create(MontgomeryModInt<T>.r);var Imag=Vector256.Create(imag._v);var xx=one;u<<=2;for(int jh=0;jh<u;){if(jh==0){int j0=0;int j1=v;int j2=v+v;int j3=j2+v;for(;j0<v;j0+=8,j1+=8,j2+=8,j3+=8){ref var T0=ref ToVector256(ref a[j0]);ref var T1=ref ToVector256(ref a[j1]);ref var T2=ref ToVector256(ref a[j2]);ref var T3=ref ToVector256(ref a[j3]);var T0P1=MontgomeryAdd(T0,T1,m2,m0);var T2P3=MontgomeryAdd(T2,T3,m2,m0);var T0M1=MontgomerySubtract(T0,T1,m2,m0);var T2M3=MontgomeryMultiply(MontgomerySubtract(T2,T3,m2,m0),Imag,r,m1);T0=MontgomeryAdd(T0P1,T2P3,m2,m0);T2=MontgomerySubtract(T0P1,T2P3,m2,m0);T1=MontgomeryAdd(T0M1,T2M3,m2,m0);T3=MontgomerySubtract(T0M1,T2M3,m2,m0);}}else{var ww=xx*xx;var yy=xx*imag;var WW=Vector256.Create(ww._v);var XX=Vector256.Create(xx._v);var YY=Vector256.Create(yy._v);int j0=jh*v;int j1=j0+v;int j2=j1+v;int j3=j2+v;int je=j1;for(;j0<je;j0+=8,j1+=8,j2+=8,j3+=8){ref var T0=ref ToVector256(ref a[j0]);ref var T1=ref ToVector256(ref a[j1]);ref var T2=ref ToVector256(ref a[j2]);ref var T3=ref ToVector256(ref a[j3]);var T0P1=MontgomeryAdd(T0,T1,m2,m0);var T2P3=MontgomeryAdd(T2,T3,m2,m0);var T0M1=MontgomeryMultiply(MontgomerySubtract(T0,T1,m2,m0),XX,r,m1);var T2M3=MontgomeryMultiply(MontgomerySubtract(T2,T3,m2,m0),YY,r,m1);T0=MontgomeryAdd(T0P1,T2P3,m2,m0);T2=MontgomeryMultiply(MontgomerySubtract(T0P1,T2P3,m2,m0),WW,r,m1);T1=MontgomeryAdd(T0M1,T2M3,m2,m0);T3=MontgomeryMultiply(MontgomerySubtract(T0M1,T2M3,m2,m0),WW,r,m1);}}xx*=dy[TrailingZeroCount(jh+=4)];}}u>>=4;v<<=2;}if((k&1)!=0){v=1<<(k-1);if(v<8){for(int j=0;j<v;++j){var ajv=a[j]-a[j+v];a[j]+=a[j+v];a[j+v]=ajv;}}else{var m0=Vector256<uint>.Zero;var m2=Vector256.Create(new T().Mod*2);int j0=0;int j1=v;for(;j0<v;j0+=8,j1+=8){ref var T0=ref ToVector256(ref a[j0]);ref var T1=ref ToVector256(ref a[j1]);var naj=MontgomeryAdd(T0,T1,m2,m0);var najv=MontgomerySubtract(T0,T1,m2,m0);T0=naj;T1=najv;}}}if(normalize){var invn=new MontgomeryModInt<T>(a.Length).Inv();for(int i=0;i<a.Length;i++)a[i]*=invn;}}[凾(512)]static StaticModInt<T>[]MultiplySimd(ReadOnlySpan<StaticModInt<T>>a,ReadOnlySpan<StaticModInt<T>>b){if(Math.Min(a.Length,b.Length)<=60)return MultiplyNative(a,b);int l=a.Length+b.Length-1;var k=InternalBit.CeilPow2(l);var M=1<<k;var buf1=new MontgomeryModInt<T>[M];var buf2=new MontgomeryModInt<T>[M];for(int i=0;i<a.Length;i++)buf1[i]=a[i].Value;for(int i=0;i<b.Length;i++)buf2[i]=b[i].Value;NttSimd(buf1);NttSimd(buf2);for(int i=0;i<buf1.Length;i++)buf1[i]._v=MontgomeryModInt<T>.Reduce((ulong)buf1[i]._v*buf2[i]._v);INttSimd(buf1,false);var invm=new MontgomeryModInt<T>(M).Inv();var res=new StaticModInt<T>[l];for(int i=0;i<res.Length;++i)res[i]=StaticModInt<T>.Raw((buf1[i]*invm).Value);return res;}}}
namespace Kzrnm.Competitive{public struct MontgomeryModInt<T>:IUtf8ConsoleWriterFormatter,IEquatable<MontgomeryModInt<T>>where T:struct,IStaticMod{static readonly T op=new T();internal static readonly uint n2=(uint)(((ulong)-op.Mod)%op.Mod);internal static readonly uint r=GetR();private static readonly MontgomeryModInt<T>One=1;internal uint _v;static uint GetR(){var mod=new T().Mod;var ret=mod;for(int i=0;i<4;++i)ret*=2-mod*ret;return ret;}public static int Mod=>(int)op.Mod;public MontgomeryModInt(long v):this(Reduce((ulong)(v%op.Mod+op.Mod)*n2)){}public MontgomeryModInt(ulong v):this(Reduce(v%op.Mod*n2)){}MontgomeryModInt(uint a){_v=a;}[凾(256)]public static implicit operator MontgomeryModInt<T>(long value)=>new MontgomeryModInt<T>(value);public int Value{[凾(256)]get{var r=Reduce(_v);return(int)(r>=op.Mod?r-op.Mod:r);}}public override string ToString()=>Value.ToString();[凾(256)]void IUtf8ConsoleWriterFormatter.Write(Utf8ConsoleWriter cw)=>cw.Write(Value);[凾(256)]public static implicit operator ConsoleOutput(MontgomeryModInt<T>m)=>m.ToConsoleOutput();[凾(256)]public static implicit operator MontgomeryModInt<T>(PropertyConsoleReader r)=>new MontgomeryModInt<T>(r.Long);[凾(256)]internal static uint Reduce(ulong b)=>(uint)((b+(ulong)((uint)b*(uint)-r)*op.Mod)>>32);[凾(256)]public static MontgomeryModInt<T>operator+(MontgomeryModInt<T>a,MontgomeryModInt<T>b){uint r=a._v+b._v-2*op.Mod;if((int)r<0)r+=2*op.Mod;return new MontgomeryModInt<T>(r);}[凾(256)]public static MontgomeryModInt<T>operator-(MontgomeryModInt<T>a,MontgomeryModInt<T>b){uint r=a._v-b._v;if((int)r<0)r+=2*op.Mod;return new MontgomeryModInt<T>(r);}[凾(256)]public static MontgomeryModInt<T>operator*(MontgomeryModInt<T>a,MontgomeryModInt<T>b)=>new MontgomeryModInt<T>(Reduce((ulong)a._v*b._v));[凾(256)]public static MontgomeryModInt<T>operator/(MontgomeryModInt<T>a,MontgomeryModInt<T>b)=>a*b.Inv();[凾(256)]public static MontgomeryModInt<T>operator+(MontgomeryModInt<T>a)=>a;[凾(256)]public static MontgomeryModInt<T>operator-(MontgomeryModInt<T>a){uint r=(uint)-a._v;if((int)r<0)r+=2*op.Mod;return new MontgomeryModInt<T>(r);}[凾(256)]public static MontgomeryModInt<T>operator ++(MontgomeryModInt<T>a)=>a+1;[凾(256)]public static MontgomeryModInt<T>operator --(MontgomeryModInt<T>a)=>a-1;[凾(256)]public MontgomeryModInt<T>Pow(long n){MontgomeryModInt<T>x=this,r=1;while(n>0){if((n&1)!=0){r*=x;}x*=x;n>>=1;}return r;}[凾(256)]public MontgomeryModInt<T>Inv()=>Pow(op.Mod-2);[凾(256)]public override bool Equals(object obj)=>obj is MontgomeryModInt<T>m&&Equals(m);[凾(256)]public bool Equals(MontgomeryModInt<T>other){var v1=_v;var v2=other._v;if(v1>=op.Mod)v1-=op.Mod;if(v2>=op.Mod)v2-=op.Mod;return v1==v2;}[凾(256)]public static bool operator==(MontgomeryModInt<T>left,MontgomeryModInt<T>right)=>Equals(left,right);[凾(256)]public static bool operator!=(MontgomeryModInt<T>left,MontgomeryModInt<T>right)=>!Equals(left,right);[凾(256)]public override int GetHashCode()=>(int)_v;public readonly struct Operator:IArithmeticOperator<MontgomeryModInt<T>>{public MontgomeryModInt<T>MultiplyIdentity=>One;[凾(256)]public MontgomeryModInt<T>Add(MontgomeryModInt<T>x,MontgomeryModInt<T>y)=>x+y;[凾(256)]public MontgomeryModInt<T>Subtract(MontgomeryModInt<T>x,MontgomeryModInt<T>y)=>x-y;[凾(256)]public MontgomeryModInt<T>Multiply(MontgomeryModInt<T>x,MontgomeryModInt<T>y)=>x*y;[凾(256)]public MontgomeryModInt<T>Divide(MontgomeryModInt<T>x,MontgomeryModInt<T>y)=>x/y;[凾(256)]MontgomeryModInt<T>IDivisionOperator<MontgomeryModInt<T>>.Modulo(MontgomeryModInt<T>x,MontgomeryModInt<T>y)=>throw new NotSupportedException();[凾(256)]public MontgomeryModInt<T>Minus(MontgomeryModInt<T>x)=>-x;[凾(256)]public MontgomeryModInt<T>Increment(MontgomeryModInt<T>x)=> ++x;[凾(256)]public MontgomeryModInt<T>Decrement(MontgomeryModInt<T>x)=> --x;}}}
namespace Kzrnm.Competitive{using static Avx2;using static Sse2;public static class SimdMontgomery{[凾(256)]public static Vector128<uint>MultiplyLow(Vector128<uint>a,Vector128<uint>b)=>Sse41.MultiplyLow(a,b);[凾(256)]public static Vector128<uint>MultiplyHigh(Vector128<uint>a,Vector128<uint>b){var a13=Shuffle(a,0xF5);var b13=Shuffle(b,0xF5);var prod02=Multiply(a,b).AsUInt32();var prod13=Multiply(a13,b13).AsUInt32();var prod=UnpackHigh(UnpackLow(prod02,prod13).AsUInt64(),UnpackHigh(prod02,prod13).AsUInt64());return prod.AsUInt32();}[凾(256)]public static Vector128<uint>MontgomeryMultiply(Vector128<uint>a,Vector128<uint>b,Vector128<uint>r,Vector128<uint>m1){return Subtract(Add(MultiplyHigh(a,b),m1),MultiplyHigh(MultiplyLow(MultiplyLow(a,b),r),m1));}[凾(256)]public static Vector128<uint>MontgomeryAdd(Vector128<uint>a,Vector128<uint>b,Vector128<uint>m2,Vector128<uint>m0){var ret=Subtract(Add(a,b),m2);return Add(And(CompareGreaterThan(m0.AsInt32(),ret.AsInt32()).AsUInt32(),m2),ret);}[凾(256)]public static Vector128<uint>MontgomerySubtract(Vector128<uint>a,Vector128<uint>b,Vector128<uint>m2,Vector128<uint>m0){var ret=Subtract(a,b);return Add(And(CompareGreaterThan(m0.AsInt32(),ret.AsInt32()).AsUInt32(),m2),ret);}[凾(256)]public static Vector256<uint>MultiplyLow(Vector256<uint>a,Vector256<uint>b)=>Avx2.MultiplyLow(a,b);[凾(256)]public static Vector256<uint>MultiplyHigh(Vector256<uint>a,Vector256<uint>b){var a13=Shuffle(a,0xF5);var b13=Shuffle(b,0xF5);var prod02=Multiply(a,b).AsUInt32();var prod13=Multiply(a13,b13).AsUInt32();var prod=UnpackHigh(UnpackLow(prod02,prod13).AsUInt64(),UnpackHigh(prod02,prod13).AsUInt64());return prod.AsUInt32();}[凾(256)]public static Vector256<uint>MontgomeryMultiply(Vector256<uint>a,Vector256<uint>b,Vector256<uint>r,Vector256<uint>m1){return Subtract(Add(MultiplyHigh(a,b),m1),MultiplyHigh(MultiplyLow(MultiplyLow(a,b),r),m1));}[凾(256)]public static Vector256<uint>MontgomeryAdd(Vector256<uint>a,Vector256<uint>b,Vector256<uint>m2,Vector256<uint>m0){var ret=Subtract(Add(a,b),m2);return Add(And(CompareGreaterThan(m0.AsInt32(),ret.AsInt32()).AsUInt32(),m2),ret);}[凾(256)]public static Vector256<uint>MontgomerySubtract(Vector256<uint>a,Vector256<uint>b,Vector256<uint>m2,Vector256<uint>m0){var ret=Subtract(a,b);return Add(And(CompareGreaterThan(m0.AsInt32(),ret.AsInt32()).AsUInt32(),m2),ret);}}}
namespace Kzrnm.Competitive{public partial class FormalPowerSeries<T>where T:struct,IStaticMod{public readonly StaticModInt<T>[]Coefficients;public int Count=>Coefficients.Length;public FormalPowerSeries(ReadOnlySpan<uint>polynomial):this(MemoryMarshal.Cast<uint,StaticModInt<T>>(polynomial)){}public FormalPowerSeries(ReadOnlySpan<int>polynomial):this(MemoryMarshal.Cast<int,StaticModInt<T>>(polynomial)){}public FormalPowerSeries(ReadOnlySpan<StaticModInt<T>>polynomial):this(Shrink(polynomial).ToArray(),true){}public FormalPowerSeries(StaticModInt<T>[]polynomial,bool newArray){if(newArray)Coefficients=(StaticModInt<T>[])polynomial.Clone();else Coefficients=polynomial;}public override string ToString()=>string.Join(", ",Coefficients);private static ReadOnlySpan<StaticModInt<T>>Shrink(ReadOnlySpan<StaticModInt<T>>polynomial){while(polynomial.Length>0&&polynomial[^1].Value==0)polynomial=polynomial[..^1];return polynomial;}[凾(256)]public static FormalPowerSeries<T>operator+(FormalPowerSeries<T>lhs,FormalPowerSeries<T>rhs){if(rhs.Coefficients.Length==0)return lhs;if(lhs.Coefficients.Length==0)return rhs;return new Impl(lhs).Add(rhs.Coefficients).ToFps();}[凾(256)]public static FormalPowerSeries<T>operator+(FormalPowerSeries<T>lhs,ReadOnlySpan<StaticModInt<T>>rhs){if(rhs.Length==0)return lhs;if(lhs.Coefficients.Length==0)return new FormalPowerSeries<T>(rhs);return new Impl(lhs).Add(rhs).ToFps();}[凾(256)]public static FormalPowerSeries<T>operator-(FormalPowerSeries<T>lhs,FormalPowerSeries<T>rhs){if(rhs.Coefficients.Length==0)return lhs;if(lhs.Coefficients.Length==0)return-rhs;return new Impl(lhs).Subtract(rhs.Coefficients).ToFps();}[凾(256)]public static FormalPowerSeries<T>operator-(FormalPowerSeries<T>lhs,ReadOnlySpan<StaticModInt<T>>rhs){if(rhs.Length==0)return lhs;if(lhs.Coefficients.Length==0)return new Impl(rhs.ToArray()).Minus().ToFps();return new Impl(lhs).Subtract(rhs).ToFps();}public static FormalPowerSeries<T>operator-(FormalPowerSeries<T>v)=>new Impl(v).Minus().ToFps();[凾(256)]public static FormalPowerSeries<T>operator*(FormalPowerSeries<T>lhs,FormalPowerSeries<T>rhs)=>new Impl(lhs).Multiply(rhs.Coefficients).ToFps();[凾(256)]public static FormalPowerSeries<T>operator*(StaticModInt<T>lhs,FormalPowerSeries<T>rhs)=>new Impl(rhs).Multiply(lhs).ToFps();[凾(256)]public static FormalPowerSeries<T>operator/(FormalPowerSeries<T>lhs,FormalPowerSeries<T>rhs)=>new Impl(lhs).Divide(rhs.Coefficients).ToFps();[凾(256)]public static FormalPowerSeries<T>operator%(FormalPowerSeries<T>lhs,FormalPowerSeries<T>rhs)=>lhs.DivRem(rhs).Remainder;[凾(256)]public(FormalPowerSeries<T>Quotient,FormalPowerSeries<T>Remainder)DivRem(FormalPowerSeries<T>other){var(q,r)=new Impl(this).DivRem(other.Coefficients);return(new FormalPowerSeries<T>(q),new FormalPowerSeries<T>(r));}[凾(256)]public static FormalPowerSeries<T>operator>>(FormalPowerSeries<T>v,int sz)=>new Impl(v).RightShift(sz).ToFps();[凾(256)]public static FormalPowerSeries<T>operator<<(FormalPowerSeries<T>v,int sz)=>new Impl(v).LeftShift(sz).ToFps();[凾(256)]public FormalPowerSeries<T>Derivative()=>new Impl(this).Derivative().ToFps();[凾(256)]public FormalPowerSeries<T>Integrate()=>new Impl(this).Integrate().ToFps();[凾(256)]public StaticModInt<T>Eval(StaticModInt<T>x){var x_n=StaticModInt<T>.Raw(1);StaticModInt<T>res=0;foreach(var c in Coefficients){res+=c*x_n;x_n*=x;}return res;}[凾(256)]public FormalPowerSeries<T>Inv(int deg=-1)=>new Impl(this).Inv(deg).ToFps();[凾(256)]public FormalPowerSeries<T>Exp(int deg=-1)=>new Impl(this).Exp(deg).ToFps();[凾(256)]public FormalPowerSeries<T>Log(int deg=-1)=>new Impl(this).Log(deg).ToFps();[凾(256)]public FormalPowerSeries<T>Pow(long k,int deg=-1)=>new Impl(this).Pow(k,deg).ToFps();}}
namespace Kzrnm.Competitive{public partial class FormalPowerSeries<T>where T:struct,IStaticMod{internal ref struct Impl{public StaticModInt<T>[]a;public int Length;public Span<StaticModInt<T>>AsSpan()=>a.AsSpan(0,Length);private Impl Set(StaticModInt<T>[]value){a=value;Length=value.Length;return this;}public Impl(FormalPowerSeries<T>fps):this((StaticModInt<T>[])fps.Coefficients.Clone()){}public Impl(StaticModInt<T>[]array){a=array;Length=array.Length;}[凾(256)]public FormalPowerSeries<T>ToFps(){var arr=a;var shrinked=Shrink(AsSpan());if(arr.Length!=shrinked.Length)arr=shrinked.ToArray();return new FormalPowerSeries<T>(arr,false);}[凾(256)]public Impl Add(ReadOnlySpan<StaticModInt<T>>rhs){ref var lp=ref a[0];ref var rp=ref MemoryMarshal.GetReference(rhs);var arr=new StaticModInt<T>[Math.Max(Length,rhs.Length)];for(int i=0;i<arr.Length;i++){var lv=i<Length?Unsafe.Add(ref lp,i):default;var rv=i<rhs.Length?Unsafe.Add(ref rp,i):default;arr[i]=lv+rv;}return Set(arr);}[凾(256)]public Impl Add(Impl rhs)=>Add(rhs.a);[凾(256)]public Impl Subtract(ReadOnlySpan<StaticModInt<T>>rhs){ref var lp=ref a[0];ref var rp=ref MemoryMarshal.GetReference(rhs);var arr=new StaticModInt<T>[Math.Max(Length,rhs.Length)];for(int i=0;i<arr.Length;i++){var lv=i<Length?Unsafe.Add(ref lp,i):default;var rv=i<rhs.Length?Unsafe.Add(ref rp,i):default;arr[i]=lv-rv;}return Set(arr);}[凾(256)]public Impl Add(StaticModInt<T>v){if(Length==0)Set(new StaticModInt<T>[]{v});else a[0]+=v;return this;}[凾(256)]public Impl Subtract(StaticModInt<T>v){if(Length==0)Set(new StaticModInt<T>[]{v});else a[0]-=v;return this;}[凾(256)]public Impl Subtract(Impl rhs)=>Subtract(rhs.a);[凾(256)]public Impl Minus(){if(Length>0){for(int i=0;i<a.Length;i++)a[i]=-a[i];}return this;}[凾(256)]public Impl Multiply(StaticModInt<T>m){for(int i=Length-1;i>=0;i--)a[i]*=m;return this;}[凾(256)]public Impl Multiply(ReadOnlySpan<StaticModInt<T>>rhs)=>Set(ConvolutionAnyMod.Convolution(AsSpan(),rhs));[凾(256)]public Impl Multiply(Impl rhs)=>Multiply(rhs.a);[凾(256)]public Impl Divide(ReadOnlySpan<StaticModInt<T>>rhs){if(Length<rhs.Length)return Set(Array.Empty<StaticModInt<T>>());if(rhs.Length<=64)return DivideNative(rhs);int n=Length-rhs.Length+1;return new Impl(ConvolutionAnyMod.Convolution(new Impl(AsSpan().ToArray()).Reverse().Pre(n).AsSpan(),new Impl(rhs.ToArray()).Reverse().Inv(n).AsSpan())).Pre(n).Reverse();}private Impl DivideNative(ReadOnlySpan<StaticModInt<T>>rhs){var f=a;var g=rhs.ToArray();var coeff=g[^1].Inv();for(int i=0;i<g.Length;i++)g[i]*=coeff;int n=f.Length-g.Length+1;var quotient=new StaticModInt<T>[n];for(int i=quotient.Length-1;i>=0;i--){quotient[i]=f[i+g.Length-1];for(int j=0;j<g.Length;j++)f[i+j]-=quotient[i]*g[j];}for(int i=0;i<quotient.Length;i++)quotient[i]*=coeff;return Set(quotient);}public(StaticModInt<T>[]Quotient,StaticModInt<T>[]Remainder)DivRem(ReadOnlySpan<StaticModInt<T>>rhs){var arr=AsSpan().ToArray();var qw=Divide(rhs);var quotient=qw.AsSpan().ToArray();var remainder=new Impl(arr).Subtract(ConvolutionAnyMod.Convolution(quotient,rhs)).AsSpan();return(quotient,remainder.ToArray());}[凾(256)]public Impl RightShift(int sz)=>sz>0?Set(AsSpan()[sz..].ToArray()):this;[凾(256)]public Impl LeftShift(int sz){if(sz==0)return this;var arr=new StaticModInt<T>[Length+sz];AsSpan().CopyTo(arr.AsSpan(sz));return Set(arr);}[凾(256)]public Impl Derivative(){if(Length>0){for(int i=1;i<a.Length;i++)a[i-1]=a[i]*StaticModInt<T>.Raw(i);--Length;}return this;}[凾(256)]public Impl Integrate(){var res=new StaticModInt<T>[Length+1];for(int i=1;i<res.Length;i++)res[i]=a[i-1]/StaticModInt<T>.Raw(i);return Set(res);}[凾(256)]public Impl Reverse(){AsSpan().Reverse();return this;}[凾(256)]public Impl Pre(int sz){if(sz<Length)Length=sz;return this;}[凾(256)]public Impl Inv(int deg=-1){if(deg<0)deg=Length;return NumberTheoreticTransform<T>.CanNtt()?InvNtt(deg):InvAnyMod(deg);}private Impl InvNtt(int deg){var r=new StaticModInt<T>[deg];r[0]=a[0].Inv();for(int d=1;d<deg;d<<=1){var f=new StaticModInt<T>[2*d];var g=new StaticModInt<T>[2*d];a.AsSpan(0,Math.Min(f.Length,Length)).CopyTo(f);r.AsSpan(0,d).CopyTo(g);NumberTheoreticTransform<T>.Ntt(f);NumberTheoreticTransform<T>.Ntt(g);for(int j=0;j<2*d;j++)f[j]*=g[j];NumberTheoreticTransform<T>.INtt(f);for(int j=0;j<d;j++)f[j]=0;NumberTheoreticTransform<T>.Ntt(f);for(int j=0;j<2*d;j++)f[j]*=g[j];NumberTheoreticTransform<T>.INtt(f);for(int j=Math.Min(r.Length,f.Length)-1;j>=d;j--)r[j]=-f[j];}return Set(r).Pre(deg);}private Impl InvAnyMod(int deg){var r=new StaticModInt<T>[1]{a[0].Inv()};for(int i=1;i<deg;i<<=1){var rp=new StaticModInt<T>[r.Length];for(int j=0;j<r.Length;j++)rp[j]=r[j]+r[j];var rc=ConvolutionAnyMod.Convolution(ConvolutionAnyMod.Convolution(r,r),a.AsSpan(0,Math.Min(Length,i<<1)));var r2=new StaticModInt<T>[1<<i];for(int j=0;j<r2.Length;j++){r2[j]=(uint)j<(uint)r.Length?r[j]+r[j]:default;if((uint)j<(uint)rc.Length)r2[j]-=rc[j];}r=r2;}return Set(r).Pre(deg);}[凾(256)]public Impl Exp(int deg=-1){if(deg<0)deg=Length;if(deg==0)return Set(new StaticModInt<T>[]{StaticModInt<T>.Raw(1)});return NumberTheoreticTransform<T>.CanNtt()?ExpNtt(deg):ExpAnyMod(deg);}[凾(256)]public Impl ExpAnyMod(int deg){var one=StaticModInt<T>.Raw(1);var ret=new Impl(new StaticModInt<T>[]{one});for(int i=1;i<deg;i<<=1){var p=new Impl(AsSpan().ToArray());var r2=new Impl(ret.AsSpan().ToArray());ret=ret.Multiply(p.Pre(i<<1).Add(one).Subtract(r2.Log(i<<1))).Pre(i<<1);}return this=ret.Pre(deg);}class SimpleDeque{StaticModInt<T>[]array;int f,t;public SimpleDeque(int size){array=new StaticModInt<T>[size*2];f=t=size;}public int Length=>t-f;[凾(256)]public void Resize(int size)=>t=f+size;[凾(256)]public void AddFirst(StaticModInt<T>v)=>array[ --f]=v;[凾(256)]public void AddLast(StaticModInt<T>v)=>array[t++]=v;[凾(256)]public void PopFirst()=> ++f;[凾(256)]public void PopLast()=> --t;[凾(256)]public Span<StaticModInt<T>>AsSpan()=>array.AsSpan(f,Length);}ref struct ExpNttInv{int Length;readonly StaticModInt<T>[]array;public ExpNttInv(int s){array=new StaticModInt<T>[s];Length=0;}[凾(256)]public void Add(StaticModInt<T>v)=>array[Length++]=v;public void InplaceIntegrate(SimpleDeque f){var mod=(int)new T().Mod;var n=f.Length;for(ref int i=ref Length;i<=n;)Add((-array[mod%i])*(mod/i));f.AddFirst(default);var fs=f.AsSpan();for(int i=1;i<fs.Length;i++)fs[i]*=array[i];}public void InplaceDerivative(SimpleDeque f){if(f.Length>0){f.PopFirst();var fs=f.AsSpan();for(int i=0;i<fs.Length;i++)fs[i]*=StaticModInt<T>.Raw(i+1);}}}[凾(256)]public Impl ExpNtt(int deg){var inv=new ExpNttInv(3*deg);inv.Add(StaticModInt<T>.Raw(0));inv.Add(StaticModInt<T>.Raw(1));var b=new SimpleDeque(3*deg);b.AddLast(1);b.AddLast(1<Length?a[1]:0);var c=new SimpleDeque(deg);c.AddLast(StaticModInt<T>.Raw(1));Span<StaticModInt<T>>z2=stackalloc StaticModInt<T>[2];z2.Fill(StaticModInt<T>.Raw(1));for(int m=2;m<deg;m*=2){var y=new StaticModInt<T>[2*m];b.AsSpan().CopyTo(y);NumberTheoreticTransform<T>.Ntt(y);var z1=z2;var z=new StaticModInt<T>[m];for(int i=0;i<z.Length;i++)z[i]=y[i]*z1[i];NumberTheoreticTransform<T>.INtt(z);z.AsSpan(0,m/2).Clear();NumberTheoreticTransform<T>.Ntt(z);for(int i=0;i<z.Length;i++)z[i]*=-z1[i];NumberTheoreticTransform<T>.INtt(z);for(int i=m/2;i<z.Length;i++)c.AddLast(z[i]);z2=new StaticModInt<T>[2*m];c.AsSpan().CopyTo(z2);NumberTheoreticTransform<T>.Ntt(z2);var x=new SimpleDeque(3*m);foreach(var v in a.AsSpan(0,Math.Min(Length,m)))x.AddLast(v);x.Resize(m);inv.InplaceDerivative(x);x.AddLast(default);{var xs=x.AsSpan();NumberTheoreticTransform<T>.Ntt(xs);for(int i=0;i<m;++i)xs[i]*=y[i];NumberTheoreticTransform<T>.INtt(xs);var bd=new Impl(b.AsSpan().ToArray()).Derivative().AsSpan();for(int i=0;i<bd.Length;i++)xs[i]-=bd[i];}x.Resize(2*m);{var xs=x.AsSpan();for(int i=0;i+1<m;++i){xs[m+i]=xs[i];xs[i]=default;}NumberTheoreticTransform<T>.Ntt(xs);for(int i=0;i<xs.Length;++i)xs[i]*=z2[i];NumberTheoreticTransform<T>.INtt(xs);}x.PopLast();inv.InplaceIntegrate(x);{var xs=x.AsSpan();for(int i=0;i<Math.Min(Length,xs.Length);++i)xs[i]+=a[i];xs[..m].Clear();NumberTheoreticTransform<T>.Ntt(xs);for(int i=0;i<xs.Length;++i)xs[i]*=y[i];NumberTheoreticTransform<T>.INtt(xs);foreach(var v in xs[m..])b.AddLast(v);}}return Set(b.AsSpan()[..deg].ToArray());}[凾(256)]public Impl Log(int deg=-1){if(deg<0)deg=Length;var inv=new Impl(AsSpan().ToArray()).Inv(deg);return Derivative().Multiply(inv).Pre(deg-1).Integrate();}[凾(256)]public Impl Pow(long k,int deg=-1){if(deg<0)deg=Length;var span=AsSpan();for(int i=0;i<span.Length;i++)if(span[i].Value!=0){if(i*k>deg)return Set(new StaticModInt<T>[deg]);var rev=span[i].Inv();var right=span[i].Pow(k);return Multiply(rev).RightShift(i).Log(deg).Multiply(k).Exp(deg).Multiply(right).LeftShift((int)(i*k)).Pre(deg);}return Set(new StaticModInt<T>[deg]);}[凾(256)]public Impl Ntt(){NumberTheoreticTransform<T>.Ntt(AsSpan());return this;}[凾(256)]public Impl INtt(){NumberTheoreticTransform<T>.INtt(AsSpan());return this;}[凾(256)]public Impl NttDoubling(){Set(NumberTheoreticTransform<T>.NttDoubling(AsSpan()));return this;}}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander

Submission Info

Judge Result