結果

問題 No.2996 Floor Sum
ユーザー KumaTachiRenKumaTachiRen
提出日時 2024-12-27 01:29:57
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 2,505 ms / 5,000 ms
コード長 39,385 bytes
コンパイル時間 21,774 ms
コンパイル使用メモリ 169,508 KB
実行使用メモリ 227,964 KB
最終ジャッジ日時 2024-12-27 01:30:27
合計ジャッジ時間 29,211 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (184 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
/home/judge/data/code/Main.cs(65,3809): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #
プレゼンテーションモードにする

using Lib;
using Lib.MathLib;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;
using static Lib.OutputLib;
public class Solver
{
const bool MultiTestCase = true;
void Solve()
{
Write(ExtFloorSum.Calc<Mod998244353>(ri, ri, ri + 1, ri, ri, ri));
}
#pragma warning disable CS0162
public Solver() { if (!MultiTestCase) Solve(); else for (int t = ri; t > 0; t--) Solve(); }
#pragma warning restore CS0162
const int IINF = 1 << 30;
const long INF = 1L << 60;
int ri { [MethodImpl(256)] get => (int)sc.Integer(); }
long rl { [MethodImpl(256)] get => sc.Integer(); }
uint rui { [MethodImpl(256)] get => (uint)sc.UInteger(); }
ulong rul { [MethodImpl(256)] get => sc.UInteger(); }
double rd { [MethodImpl(256)] get => sc.Double(); }
string rs { [MethodImpl(256)] get => sc.Scan(); }
string rline { [MethodImpl(256)] get => sc.Line(); }
public StreamScanner sc = new StreamScanner(Console.OpenStandardInput());
void ReadArray(out int[] a, int n) { a = new int[n]; for (int i = 0; i < a.Length; i++) a[i] = ri; }
void ReadArray(out long[] a, int n) { a = new long[n]; for (int i = 0; i < a.Length; i++) a[i] = rl; }
void ReadArray<T>(out T[] a, int n, Func<T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(); }
void ReadArray<T>(out T[] a, int n, Func<int, T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(i); }
}
static class Program
{
static public void Main(string[] args)
{
SourceExpander.Expander.Expand();
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
new Solver();
Console.Out.Flush();
}
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace Lib.FpsLib{public static class Inv{[MethodImpl(256)]public static StaticModInt<Mod>[]Calc<Mod>(ReadOnlySpan<StaticModInt<Mod>>a,int deg=-1
    )where Mod:struct,IStaticMod{if(deg==-1)deg=a.Length;if(deg==0)return Array.Empty<StaticModInt<Mod>>();int n=(int)BitOperations.RoundUpToPowerOf2
    ((uint)deg);var f0=new StaticModInt<Mod>[n];var g0=new StaticModInt<Mod>[n];var r=new StaticModInt<Mod>[deg];r[0]=a[0].Inv();var inv4=new
    StaticModInt<Mod>(4).Inv();var c=StaticModInt<Mod>.One;for(int i=1;i<n;i<<=1){c*=inv4;var f=f0.AsSpan(0,i<<1);a[..Math.Min(a.Length,i<<1)].CopyTo
    (f);if(a.Length<(i<<1))f[a.Length..].Clear();if(i<=(1<<6)){for(int j=(i<<1)-1;j>=0;j--){StaticModInt<Mod>v=0;for(int l=0;l<i&&l<=j;l++)v+=f[j-l]
    *r[l];f[j]=v;}for(int j=(i<<1)-1;j>=i;j--){StaticModInt<Mod>v=0;for(int l=0;l<i&&l<=j;l++)v+=f[j-l]*r[l];f[j]=-v;}if(f.Length>deg)f=f.Slice(0,deg
    );f[i..].CopyTo(r.AsSpan(i));}else{var g=g0.AsSpan(0,i<<1);r.AsSpan(0,i).CopyTo(g);ACLButterfly<Mod>.Calculate(f);ACLButterfly<Mod>.Calculate(g
    );for(int j=0;j<f.Length;j++)f[j]*=g[j];ACLButterfly<Mod>.CalculateInv(f);f[..i].Clear();ACLButterfly<Mod>.Calculate(f);for(int j=0;j<f.Length;j
    ++)f[j]*=g[j];ACLButterfly<Mod>.CalculateInv(f);if(f.Length>deg)f=f.Slice(0,deg);for(int j=i;j<f.Length;j++)r[j]=-f[j]*c;}}return r;}}}
public interface IField<T>where T:IField<T>{public static abstract T operator-(T x);public static abstract T operator+(T l,T r);public static abstract
    T operator-(T l,T r);public static abstract T operator*(T l,T r);public static abstract T operator/(T l,T r);public static abstract T Zero{get
    ;}public static abstract T One{get;}public static abstract bool IsZero(T x);public static abstract bool IsOne(T x);}
namespace Lib{public static class InternalBit{[MethodImpl(256)]public static uint ExtractLowestSetBit(int n){if(System.Runtime.Intrinsics.X86.Bmi1
    .IsSupported)return System.Runtime.Intrinsics.X86.Bmi1.ExtractLowestSetBit((uint)n);return(uint)(n&-n);}[MethodImpl(256)]public static int Bsf
    (uint n){return BitOperations.TrailingZeroCount(n);}[MethodImpl(256)]public static int CeilPow2(int n){var un=(uint)n;if(un<=1)return 0;return
    BitOperations.Log2(un-1)+1;}}}
namespace Lib{public partial class StreamScanner{public StreamScanner(Stream stream){str=stream;}private readonly Stream str;private readonly
    byte[]buf=new byte[1024];private int len,ptr;public bool isEof=false;public bool IsEndOfStream{get{return isEof;}}[MethodImpl(256)]private byte
    Read(){if(isEof)throw new EndOfStreamException();if(ptr>=len){ptr=0;if((len=str.Read(buf,0,1024))<=0){isEof=true;return 0;}}return buf[ptr++]
    ;}[MethodImpl(256)]public char Char(){byte b;do b=Read();while(b<33||126<b);return(char)b;}[MethodImpl(256)]public string Line(){var sb=new
    StringBuilder();for(var b=Char();b!=10&&!isEof;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]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(256)]public long Integer(){long ret=0
    ;var ng=false;byte b;do b=Read();while(b!='-'&&(b<'0'||'9'<b));if(b=='-'){ng=true;b=Read();}for(;'0'<=b&&b<='9';b=Read())ret=ret*10+(b^'0');return
    ng?-ret:ret;}[MethodImpl(256)]public ulong UInteger(){ulong ret=0;byte b;do b=Read();while(b<'0'||'9'<b);for(;'0'<=b&&b<='9';b=Read())ret=ret*10
    +(ulong)(b^'0');return ret;}[MethodImpl(256)]public double Double()=>double.Parse(Scan());}}
namespace Lib.MathLib{public static class Convolution{[MethodImpl(256)]public static uint[]Calc<TMod>(ReadOnlySpan<uint>a,ReadOnlySpan<uint>b)where
    TMod:struct,IStaticMod{var u=new StaticModInt<TMod>[a.Length];for(int i=0;i<a.Length;i++)u[i]=a[i];var v=new StaticModInt<TMod>[b.Length];for(int
    i=0;i<b.Length;i++)v[i]=b[i];u=Calc<TMod>(u,v);var r=new uint[u.Length];for(int i=0;i<u.Length;i++)r[i]=(uint)u[i].Value;return r;}[MethodImpl(256
    )]public static long[]Calc<TMod>(ReadOnlySpan<long>a,ReadOnlySpan<long>b)where TMod:struct,IStaticMod{var u=new StaticModInt<TMod>[a.Length];for
    (int i=0;i<a.Length;i++)u[i]=a[i];var v=new StaticModInt<TMod>[b.Length];for(int i=0;i<b.Length;i++)v[i]=b[i];u=Calc<TMod>(u,v);var r=new long[u
    .Length];for(int i=0;i<u.Length;i++)r[i]=u[i];return r;}[MethodImpl(256)]public static StaticModInt<TMod>[]Calc<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)<=30)return Naive(a,b);return FFT(a,b);}[MethodImpl(256)]public static StaticModInt<TMod>[]Calc<TMod
    >(StaticModInt<TMod>[]a,StaticModInt<TMod>[]b)where TMod:struct,IStaticMod=>Calc((ReadOnlySpan<StaticModInt<TMod>>)a,b);[MethodImpl(256)]public
    static StaticModInt<TMod>[]Square<TMod>(ReadOnlySpan<StaticModInt<TMod>>a)where TMod:struct,IStaticMod{var n=a.Length;if(n==0)return Array.Empty
    <StaticModInt<TMod>>();if(n<=30)return Naive(a,a);return SquareFFT(a);}[MethodImpl(256)]private static StaticModInt<TMod>[]SquareFFT<TMod
    >(ReadOnlySpan<StaticModInt<TMod>>a)where TMod:struct,IStaticMod{int n=a.Length;int len=2*n-1;int z=1<<InternalBit.CeilPow2(len);var a2=new
    StaticModInt<TMod>[z];a.CopyTo(a2);Butterfly<TMod>.Calculate(a2);for(int i=0;i<a2.Length;i++)a2[i]*=a2[i];Butterfly<TMod>.CalculateInv(a2);var r
    =a2[..len];var iz=new StaticModInt<TMod>(z).Inv();foreach(ref var x in r.AsSpan())x*=iz;return r;}[MethodImpl(256)]private static StaticModInt
    <TMod>[]FFT<TMod>(ReadOnlySpan<StaticModInt<TMod>>a,ReadOnlySpan<StaticModInt<TMod>>b)where TMod:struct,IStaticMod{int n=a.Length,m=b.Length;int
    len=n+m-1;int z=1<<InternalBit.CeilPow2(len);var a2=new StaticModInt<TMod>[z];var b2=new StaticModInt<TMod>[z];a.CopyTo(a2);b.CopyTo(b2);Butterfly
    <TMod>.Calculate(a2);Butterfly<TMod>.Calculate(b2);for(int i=0;i<a2.Length;i++)a2[i]*=b2[i];Butterfly<TMod>.CalculateInv(a2);var r=a2[..len];var
    iz=new StaticModInt<TMod>(z).Inv();foreach(ref var x in r.AsSpan())x*=iz;return r;}[MethodImpl(256)]private static StaticModInt<TMod>[]Naive<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
    ;}[MethodImpl(256)]public static long[]Long(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=Calc<FFTMod1>(a,b);var c2=Calc<FFTMod2>(a,b);var c3=Calc<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
    ;}}[MethodImpl(256)]public static StaticModInt<Mod>[]IntMod<Mod>(ReadOnlySpan<StaticModInt<Mod>>a,ReadOnlySpan<StaticModInt<Mod>>b)where Mod
    :struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0)return Array.Empty<StaticModInt<Mod>>();const long Mod1=754974721;const long Mod2
    =167772161;const long Mod3=469762049;const long M1invM2=95869806;const long M12invM3=187290749;int mod=StaticModInt<Mod>.Mod;long M12mod=Mod1
    *Mod2%mod;var u=new long[n];for(int i=0;i<n;i++)u[i]=a[i];var v=new long[m];for(int i=0;i<m;i++)v[i]=b[i];var c1=Calc<FFTMod1>(u,v);var c2=Calc
    <FFTMod2>(u,v);var c3=Calc<FFTMod3>(u,v);var c=new StaticModInt<Mod>[n+m-1];for(int i=0;i<c.Length;i++){long v1=(c2[i]-c1[i])*M1invM2%Mod2;if(v1<0
    )v1+=Mod2;long v2=(c3[i]-(c1[i]+Mod1*v1)%Mod3)*M12invM3%Mod3;if(v2<0)v2+=Mod3;long v3=(c1[i]+Mod1*v1+M12mod*v2)%mod;if(v3<0)v3+=mod;c[i]=v3
    ;}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 Lib.MathLib{public static class ExtFloorSum{static long Floor(long a,long b)=>a>=0?a/b:(a+1)/b-1;public static StaticModInt<Mod>Calc<Mod
    >(int p,int q,long n,long m,long a,long b)where Mod:struct,IStaticMod{int sz=p+q+1;var fact=new ModFact<Mod>(sz);var be=BernoulliNumber.Table<Mod
    >(sz);for(int i=1;i<be.Length;i+=2)be[i]=-be[i];for(int i=0;i<be.Length;i++)be[i]*=fact.FactInv(i);var e1=new StaticModInt<Mod>[sz];for(int i=1;i
    <sz;i++)e1[i]=fact.FactInv(i);var st=new Stack<(bool post,long N,long M,long A,long B)>();var f=new StaticModInt<Mod>[sz][];for(int i=0;i<sz;i
    ++)f[i]=new StaticModInt<Mod>[sz-i];st.Push((false,n,m,a,b));while(st.Count>0){var(post,N,M,A,B)=st.Pop();if(N==0){continue;}else if(!post){st
    .Push((true,N,M,A,B));if(A!=0){A-=Floor(A,M)*M;B-=Floor(B,M)*M;long k=Floor(A*(N-1)+B,M);st.Push((false,k,A,M,M-B-1));}}else{long aq=Floor(A,M);A
    -=aq*M;long bq=Floor(B,M);B-=bq*M;if(A==0){long c=Floor(B,M);for(int i=0;i<sz;i++){ref var sum=ref f[i][0];StaticModInt<Mod>pow=N-1;for(int j=1;j
    <=i+1;j++,pow*=N-1)sum+=pow*fact.FactInv(j)*be[i+1-j];sum*=fact.Fact(i);if(i==0)sum+=1;for(int j=1;j<sz-i;j++)f[i][j]=f[i][j-1]*c;}}else{long k
    =Floor(A*(N-1)+B,M);{var g=new StaticModInt<Mod>[sz][];for(int i=0;i<g.Length;i++)g[i]=new StaticModInt<Mod>[sz-i];for(int i=0;i<f.Length;i++){for
    (int j=1;j<f[i].Length;j++)f[i][j]*=fact.FactInv(i)*fact.FactInv(j);if(f[i].Length==1){Array.Clear(f[i]);}else{f[i]=Convolution.Calc<Mod>(f[i]
    .AsSpan(1),be.AsSpan(0,f[i].Length))[..f[i].Length];}for(int j=0;j<f[i].Length;j++)g[j][i]=f[i][j];}f=g;}for(int i=0;i<f.Length;i++)f[i]
    =Convolution.Calc<Mod>(f[i],e1.AsSpan(0,f[i].Length))[..f[i].Length];for(int i=0;i<f.Length;i++){StaticModInt<Mod>sum=0,pow=N-1;for(int j=1;j<=i+1
    ;j++,pow*=N-1)sum+=pow*fact.FactInv(j)*be[i+1-j];sum*=fact.Fact(i);pow=1;for(int j=0;j<f[i].Length;j++,pow*=k)f[i][j]=sum*pow-fact.Fact(i)*fact
    .Fact(j)*f[i][j];}f[0][0]+=1;}if(aq!=0){var g=new StaticModInt<Mod>[sz][];for(int i=0;i<sz;i++){g[i]=new StaticModInt<Mod>[sz-i];for(int j=0;j<sz
    -i;j++){ref var v=ref g[i][j];StaticModInt<Mod>pow=1;for(int k=0;k<=j;k++,pow*=aq)v+=fact.Binom(j,k)*pow*f[i+k][j-k];}}f=g;}if(bq!=0){var g=new
    StaticModInt<Mod>[sz][];for(int i=0;i<sz;i++){g[i]=new StaticModInt<Mod>[sz-i];for(int j=0;j<sz-i;j++){ref var v=ref g[i][j];StaticModInt<Mod>pow
    =1;for(int k=0;k<=j;k++,pow*=bq)v+=fact.Binom(j,k)*pow*f[i][j-k];}}f=g;}}}return f[p][q];}}}
namespace Lib{public static class ACLButterfly<Mod>where Mod:struct,IStaticMod{public static uint mod{get;private set;}static uint g;static int rank2
    ;static StaticModInt<Mod>[]root,iroot;static StaticModInt<Mod>[]rate2,irate2;static StaticModInt<Mod>[]rate3,irate3;readonly static bool
    Initialized=Init();static uint[]buf;static bool Init(){buf=new uint[Vector<uint>.Count];mod=default(Mod).Mod;g=(uint)InternalMath.PrimitiveRoot
    <Mod>();rank2=BitOperations.TrailingZeroCount(mod-1);root=new StaticModInt<Mod>[rank2+1];iroot=new StaticModInt<Mod>[rank2+1];rate2=new
    StaticModInt<Mod>[Math.Max(0,rank2-2+1)];irate2=new StaticModInt<Mod>[Math.Max(0,rank2-2+1)];rate3=new StaticModInt<Mod>[Math.Max(0,rank2-3+1)]
    ;irate3=new StaticModInt<Mod>[Math.Max(0,rank2-3+1)];root[rank2]=new StaticModInt<Mod>(g).Pow((mod-1)>>rank2);iroot[rank2]=root[rank2].Inv();for
    (int i=rank2-1;i>=0;i--){root[i]=root[i+1]*root[i+1];iroot[i]=iroot[i+1]*iroot[i+1];}{ulong prod=1,iprod=1;for(int i=0;i<=rank2-2;i++){rate2[i]
    =root[i+2]*prod;irate2[i]=iroot[i+2]*iprod;prod*=iroot[i+2];iprod*=root[i+2];}}{ulong prod=1,iprod=1;for(int i=0;i<=rank2-3;i++){rate3[i]=root[i
    +3]*prod;irate3[i]=iroot[i+3]*iprod;prod*=iroot[i+3];iprod*=root[i+3];}}return true;}[MethodImpl(256)]public static void Calculate(Span
    <StaticModInt<Mod>>a){int n=a.Length;int h=BitOperations.TrailingZeroCount(n);var regLength=Vector<uint>.Count;var modV=new Vector<uint>(mod);int
    len=0;while(len<h){if(h-len==1){int p=1<<(h-len-1);StaticModInt<Mod>rot=1;if(p<regLength){for(int s=0;s<(1<<len);s++){int offset=s<<(h-len);var f0
    =a.Slice(offset,p);var f1=a.Slice(offset+p,p);for(int i=0;i<p;i++){var a0=f0[i];var a1=f1[i]*rot;f0[i]=a0+a1;f1[i]=a0-a1;}if(s+1!=(1<<len))rot
    *=rate2[BitOperations.TrailingZeroCount(~s)];}}else{for(int s=0;s<(1<<len);s++){int offset=s<<(h-len);var f0=a.Slice(offset,p);var f1=a.Slice
    (offset+p,p);foreach(ref var x in f1)x*=rot;for(int i=0;i<f0.Length;i+=regLength){var g0=MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f0.Slice(i
    ));var g1=MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f1.Slice(i));var v0=new Vector<uint>(g0);var v1=new Vector<uint>(g1);var add=v0+v1;var sub=v0
    -v1;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(g0);sub.CopyTo(g1);}if(s+1!=(1<<len))rot*=rate2[BitOperations.TrailingZeroCount(~s)];}}len
    ++;}else{int p=1<<(h-len-2);StaticModInt<Mod>rot=1,imag=root[2];if(p<regLength){for(int s=0;s<(1<<len);s++){StaticModInt<Mod>rot2=rot*rot
    ;StaticModInt<Mod>rot3=rot2*rot;int offset=s<<(h-len);var f0=a.Slice(offset,p);var f1=a.Slice(offset+p,p);var f2=a.Slice(offset+2*p,p);var f3=a
    .Slice(offset+3*p,p);for(int i=0;i<p;i++){ulong mod2=(ulong)mod*mod;ulong a0=f0[i];ulong a1=f1[i]*rot;ulong a2=f2[i]*rot2;ulong a3=f3[i]*rot3
    ;ulong a1na3imag=(a1+mod2-a3)%mod*imag;ulong na2=mod2-a2;f0[i]=a0+a2+a1+a3;f1[i]=a0+a2+(2*mod2-(a1+a3));f2[i]=a0+na2+a1na3imag;f3[i]=a0+na2+(mod2
    -a1na3imag);}if(s+1!=(1<<len))rot*=rate3[BitOperations.TrailingZeroCount(~s)];}}else{for(int s=0;s<(1<<len);s++){StaticModInt<Mod>rot2=rot*rot
    ;StaticModInt<Mod>rot3=rot2*rot;int offset=s<<(h-len);var f0=a.Slice(offset,p);var f1=a.Slice(offset+p,p);var f2=a.Slice(offset+2*p,p);var f3=a
    .Slice(offset+3*p,p);foreach(ref var x in f1)x*=rot;foreach(ref var x in f2)x*=rot2;foreach(ref var x in f3)x*=rot3;for(int i=0;i<f0.Length;i
    +=regLength){var g0=MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f0.Slice(i));var g1=MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f1.Slice(i));var g2
    =MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f2.Slice(i));var g3=MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f3.Slice(i));var v0=new Vector<uint>(g0
    );var v1=new Vector<uint>(g1);var v2=new Vector<uint>(g2);var v3=new Vector<uint>(g3);var add02=v0+v2;var sub02=v0-v2;var add13=v1+v3;var sub13=v1
    -v3;var ge=Vector.GreaterThanOrEqual(add02,modV);add02=Vector.ConditionalSelect(ge,add02-modV,add02);ge=Vector.GreaterThanOrEqual(sub02,modV
    );sub02=Vector.ConditionalSelect(ge,sub02+modV,sub02);ge=Vector.GreaterThanOrEqual(add13,modV);add13=Vector.ConditionalSelect(ge,add13-modV,add13
    );ge=Vector.GreaterThanOrEqual(sub13,modV);sub13=Vector.ConditionalSelect(ge,sub13+modV,sub13);sub13.CopyTo(buf);foreach(ref var x in buf.AsSpan
    ())x=(uint)(x*imag%mod);sub13=new Vector<uint>(buf);var w=add02+add13;ge=Vector.GreaterThanOrEqual(w,modV);w=Vector.ConditionalSelect(ge,w-modV,w
    );w.CopyTo(g0);w=add02-add13;ge=Vector.GreaterThanOrEqual(w,modV);w=Vector.ConditionalSelect(ge,w+modV,w);w.CopyTo(g1);w=sub02+sub13;ge=Vector
    .GreaterThanOrEqual(w,modV);w=Vector.ConditionalSelect(ge,w-modV,w);w.CopyTo(g2);w=sub02-sub13;ge=Vector.GreaterThanOrEqual(w,modV);w=Vector
    .ConditionalSelect(ge,w+modV,w);w.CopyTo(g3);}if(s+1!=(1<<len))rot*=rate3[BitOperations.TrailingZeroCount(~s)];}}len+=2;}}}[MethodImpl(256)]public
    static void CalculateInv(Span<StaticModInt<Mod>>a){int n=a.Length;var regLength=Vector<uint>.Count;var modV=new Vector<uint>(mod);int h
    =BitOperations.TrailingZeroCount(n);int len=h;while(len>0){if(len==1){int p=1<<(h-len);StaticModInt<Mod>irot=1;if(p<regLength){for(int s=0;s<(1
    <<(len-1));s++){int offset=s<<(h-len+1);var f0=a.Slice(offset,p);var f1=a.Slice(offset+p,p);for(int i=0;i<p;i++){StaticModInt<Mod>a0=f0[i]
    ;StaticModInt<Mod>a1=f1[i];f0[i]=a0+a1;f1[i]=(a0-a1)*irot;}if(s+1!=(1<<(len-1)))irot*=irate2[BitOperations.TrailingZeroCount(~s)];}}else{for(int s
    =0;s<(1<<(len-1));s++){int offset=s<<(h-len+1);var f0=a.Slice(offset,p);var f1=a.Slice(offset+p,p);for(int i=0;i<f0.Length;i+=regLength){var g0
    =MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f0.Slice(i));var g1=MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f1.Slice(i));var v0=new Vector<uint>(g0
    );var v1=new Vector<uint>(g1);var add=v0+v1;var sub=v0-v1;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(g0);sub.CopyTo(g1);}foreach(ref var x in f1)x
    *=irot;if(s+1!=(1<<(len-1)))irot*=irate2[BitOperations.TrailingZeroCount(~s)];}}len--;}else{int p=1<<(h-len);StaticModInt<Mod>irot=1,iimag
    =iroot[2];if(p<regLength){for(int s=0;s<(1<<(len-2));s++){StaticModInt<Mod>irot2=irot*irot;StaticModInt<Mod>irot3=irot2*irot;int offset=s<<(h-len
    +2);var f0=a.Slice(offset,p);var f1=a.Slice(offset+p,p);var f2=a.Slice(offset+2*p,p);var f3=a.Slice(offset+3*p,p);for(int i=0;i<p;i++){ulong a0
    =f0[i];ulong a1=f1[i];ulong a2=f2[i];ulong a3=f3[i];ulong a2na3iimag=(mod+a2-a3)*iimag;f0[i]=a0+a1+a2+a3;f1[i]=(a0+(mod-a1)+a2na3iimag)*irot;f2[i]
    =(a0+a1+(mod-a2)+(mod-a3))*irot2;f3[i]=(a0+(mod-a1)+(mod-a2na3iimag))*irot3;}if(s+1!=(1<<(len-2)))irot*=irate3[BitOperations.TrailingZeroCount(~s
    )];}}else{for(int s=0;s<(1<<(len-2));s++){StaticModInt<Mod>irot2=irot*irot;StaticModInt<Mod>irot3=irot2*irot;int offset=s<<(h-len+2);var f0=a
    .Slice(offset,p);var f1=a.Slice(offset+p,p);var f2=a.Slice(offset+2*p,p);var f3=a.Slice(offset+3*p,p);for(int i=0;i<f0.Length;i+=regLength){var g0
    =MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f0.Slice(i));var g1=MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f1.Slice(i));var g2=MemoryMarshal.Cast
    <StaticModInt<Mod>,uint>(f2.Slice(i));var g3=MemoryMarshal.Cast<StaticModInt<Mod>,uint>(f3.Slice(i));var v0=new Vector<uint>(g0);var v1=new Vector
    <uint>(g1);var v2=new Vector<uint>(g2);var v3=new Vector<uint>(g3);var add01=v0+v1;var sub01=v0-v1;var add23=v2+v3;var sub23=v2-v3;var ge=Vector
    .GreaterThanOrEqual(add01,modV);add01=Vector.ConditionalSelect(ge,add01-modV,add01);ge=Vector.GreaterThanOrEqual(sub01,modV);sub01=Vector
    .ConditionalSelect(ge,sub01+modV,sub01);ge=Vector.GreaterThanOrEqual(add23,modV);add23=Vector.ConditionalSelect(ge,add23-modV,add23);ge=Vector
    .GreaterThanOrEqual(sub23,modV);sub23=Vector.ConditionalSelect(ge,sub23+modV,sub23);sub23.CopyTo(buf);foreach(ref var x in buf.AsSpan())x=(uint)(x
    *iimag%mod);sub23=new Vector<uint>(buf);var w=add01+add23;ge=Vector.GreaterThanOrEqual(w,modV);w=Vector.ConditionalSelect(ge,w-modV,w);w.CopyTo(g0
    );w=sub01+sub23;ge=Vector.GreaterThanOrEqual(w,modV);w=Vector.ConditionalSelect(ge,w-modV,w);w.CopyTo(g1);w=add01-add23;ge=Vector
    .GreaterThanOrEqual(w,modV);w=Vector.ConditionalSelect(ge,w+modV,w);w.CopyTo(g2);w=sub01-sub23;ge=Vector.GreaterThanOrEqual(w,modV);w=Vector
    .ConditionalSelect(ge,w+modV,w);w.CopyTo(g3);}foreach(ref var x in f1)x*=irot;foreach(ref var x in f2)x*=irot2;foreach(ref var x in f3)x*=irot3;if
    (s+1!=(1<<(len-2)))irot*=irate3[BitOperations.TrailingZeroCount(~s)];}}len-=2;}}}}}
namespace Lib{public class Barrett{public readonly uint Mod;public readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1
    ;}[MethodImpl(256)]public uint Mul(uint a,uint b)=>Reduce((ulong)a*b);[MethodImpl(256)]public uint Reduce(ulong z){var x=InternalMath.Mul128Bit(z
    ,IM);var v=unchecked((uint)(z-x*Mod));if(Mod<=v)v+=Mod;return v;}[MethodImpl(256)]public uint Pow(long x,long n){if(Mod==1)return 0;uint r=1,y
    =(uint)InternalMath.SafeMod(x,Mod);while(n>0){if((n&1)!=0)r=Mul(r,y);y=Mul(y,y);n>>=1;}return r;}}}
namespace Lib{public static class Butterfly<T>where T:struct,IStaticMod{static readonly List<int[]>bit_reversal=new List<int[]>();public static
    ReadOnlySpan<int>GetBitReversalArray(int log){for(int l=bit_reversal.Count;l<=log;l++){var rev=new int[1<<l];for(int i=0;i<rev.Length;i++)rev[i]
    =(rev[i>>1]>>1)|((i&1)<<(l-1));bit_reversal.Add(rev);}return bit_reversal[log];}public static StaticModInt<T>GetRoot(int log){int g=InternalMath
    .PrimitiveRoot<T>();var z=new StaticModInt<T>(g).Pow((default(T).Mod-1)>>log);return z;}public static readonly StaticModInt<T>[]sumE=CalcurateSumE
    ();public static readonly StaticModInt<T>[]sumIE=CalcurateSumIE();public static readonly uint Mod=default(T).Mod;[MethodImpl(256)]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>(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)];}}}[MethodImpl
    (256)]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>(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)(Mod+l.Value-r.Value)*(ulong)iNow.Value%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)];}}}public 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;}public 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("Array length must be a power of 2.");}}public static void Doubling(ReadOnlySpan
    <StaticModInt<T>>a,Span<StaticModInt<T>>b){int n=a.Length;var c=b[n..];a.CopyTo(b);a.CopyTo(c);CalculateInv(c);int g=InternalMath.PrimitiveRoot<T
    >();var z=new StaticModInt<T>(g).Pow((default(T).Mod-1)/(2*n));StaticModInt<T>w=1;for(int i=0;i<c.Length;i++,w*=z)c[i]*=w;Calculate(c);foreach(ref
    var v in b[..n])v*=n;}}}
namespace Lib{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}};[MethodImpl(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{var m=default(TMod).Mod;Span<uint>divs=stackalloc uint[20];divs[0]
    =2;int cnt=1;var x=m-1;x>>=BitOperations.TrailingZeroCount(x);for(uint i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;do{x/=i;}while(x%i==0);}}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:;}}[MethodImpl(256)]public static int PrimitiveRoot(uint m){if(primitiveRootsCache.TryGetValue(m,out var p))return p;return
    primitiveRootsCache[m]=PrimitiveRootCalculate(m);}static int PrimitiveRootCalculate(uint m){Span<uint>divs=stackalloc uint[20];divs[0]=2;int cnt=1
    ;var x=m-1;x>>=BitOperations.TrailingZeroCount(x);for(uint i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;do{x/=i;}while(x%i==0);}}if(x>1
    ){divs[cnt++]=x;}divs=divs.Slice(0,cnt);ulong Pow(ulong x,uint n){ulong y=1;while(n>0){if((n&1)==1)y=y*x%m;x=x*x%m;n/=2;}return y;}for(uint g=2;;g
    ++){foreach(var d in divs)if(Pow(g,(m-1)/d)==1)goto NEXT;return(int)g;NEXT:;}}[MethodImpl(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;}}[MethodImpl(256)]public static long SafeMod(long x,long m){x%=m;if(x<0)x+=m;return x
    ;}[MethodImpl(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;}[MethodImpl(256)]public static uint PowMod(long x,long n,int m){if(m==1)return 0
    ;return new Barrett((uint)m).Pow(x,n);}[MethodImpl(256)]public static uint PowMod(long x,long n,uint m){if(m==1)return 0;return new Barrett(m).Pow
    (x,n);}[MethodImpl(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);}}[MethodImpl(256)]public static ulong
    Mul128Bit(ulong a,ulong b){if(System.Runtime.Intrinsics.X86.Bmi2.X64.IsSupported)return System.Runtime.Intrinsics.X86.Bmi2.X64.MultiplyNoFlags(a,b
    );return Mul128BitLogic(a,b);}[MethodImpl(256)]internal static ulong Mul128BitLogic(ulong a,ulong b){var au=a>>32;var ad=a&0xFFFFFFFF;var bu=b>>32
    ;var bd=b&0xFFFFFFFF;var l=ad*bd;var m1=au*bd;var m2=ad*bu;var h=au*bu;var lu=l>>32;var m1d=m1&0xFFFFFFFF;var m2d=m2&0xFFFFFFFF;var c=m1d+m2d+lu
    ;return h+(m1>>32)+(m2>>32)+(c>>32);}}}
namespace Lib.MathLib{public static class LinearSieve{public static List<int>Primes;public static int[]LPF;public static int[]Table(int max){Calc(max
    );int l=Primes.Count;while(l>0&&Primes[l-1]>max)l--;var ret=new int[l];for(int i=0;i<l;i++)ret[i]=Primes[i];return ret;}public static void Calc
    (int max){if(Primes==null){Primes=new List<int>();LPF=new int[max+1];CalcInner(2,max);}else if(LPF.Length-1<max){int min=LPF.Length;Array.Resize
    (ref LPF,max+1);CalcInner(min,max);}}private static void CalcInner(int min,int max){for(int d=2;d<min;d++)for(int j=0;j<Primes.Count;j++){int p
    =Primes[j];if((long)p*d>max||p>LPF[d])break;LPF[(long)p*d]=p;}for(int d=min;d<=max;d++){if(LPF[d]==0){LPF[d]=d;Primes.Add(d);}for(int j=0;j<Primes
    .Count;j++){int p=Primes[j];if((long)p*d>max||p>LPF[d])break;LPF[(long)p*d]=p;}}}}}
namespace Lib.MathLib{public static class BernoulliNumber{public static StaticModInt<Mod>[]Table<Mod>(int n)where Mod:struct,IStaticMod{var e=new
    StaticModInt<Mod>[n+1];e[n]=1;for(int i=2;i<=n+1;i++)e[n]*=i;e[n]=e[n].Inv();for(int i=n;i>0;i--)e[i-1]=e[i]*(i+1);var b=FpsLib.Inv.Calc<Mod>(e,n
    +1);StaticModInt<Mod>fact=1;for(int i=2;i<=n;i++)b[i]*=(fact*=i);return b;}public static StaticModInt<Mod>Arbitrary<Mod>(int n)where Mod:struct
    ,IStaticMod{if(n==0)return 1;if(n==1)return new StaticModInt<Mod>(-2).Inv();if(n==2)return new StaticModInt<Mod>(6).Inv();if(n%2==1)return 0
    ;LinearSieve.Calc(n);var lpf=LinearSieve.LPF;var primes=LinearSieve.Primes;var pow=new StaticModInt<Mod>[n+1];pow[1]=1;for(int i=2;i<=n;i++){if
    (lpf[i]==i)pow[i]=new StaticModInt<Mod>(i).Pow(n);for(int j=0;j<primes.Count;j++){int p=primes[j];if(p*i>n||p>lpf[i])break;pow[p*i]=pow[p]*pow[i]
    ;}}var fact=new ModFact<Mod>(n+1);StaticModInt<Mod>ret=0,a=0;for(int i=0;i<=n;i++)a+=fact.Inv(i+1);for(int i=1;i<=n;i++){if(i%2==0)a+=fact.Binom(n
    +1,i)*fact.Inv(i);else a-=fact.Binom(n+1,i)*fact.Inv(i);ret+=a*pow[i];}return ret;}}}
namespace Lib{public class ModFact<TMod>where TMod:struct,IStaticMod{static StaticModInt<TMod>[]fact;static StaticModInt<TMod>[]factinv;static
    StaticModInt<TMod>[]inv;public ModFact(long n){if(fact==null){fact=new StaticModInt<TMod>[n+1];factinv=new StaticModInt<TMod>[n+1];inv=new
    StaticModInt<TMod>[n+1];fact[0]=1;for(long i=0;i<n;i++)fact[i+1]=fact[i]*(i+1);factinv[n]=fact[n].Inv();for(long i=n;i>0;i--)factinv[i-1]
    =factinv[i]*i;for(long i=1;i<=n;i++)inv[i]=fact[i-1]*factinv[i];}else if(fact.Length<=n)Resize(n);}static void Resize(long n){int m=fact.Length;n
    =Math.Max(n,m*2);Array.Resize(ref fact,(int)n+1);Array.Resize(ref factinv,(int)n+1);Array.Resize(ref inv,(int)n+1);for(long i=m-1;i<n;i++)fact[i
    +1]=fact[i]*(i+1);factinv[n]=fact[n].Inv();for(long i=n;i>m;i--)factinv[i-1]=factinv[i]*i;for(long i=m;i<=n;i++)inv[i]=fact[i-1]*factinv[i]
    ;}[MethodImpl(256)]public StaticModInt<TMod>Fact(long n){if(fact.Length<=n)Resize(n);return fact[n];}[MethodImpl(256)]public StaticModInt<TMod
    >FactInv(long n){if(fact.Length<=n)Resize(n);return factinv[n];}[MethodImpl(256)]public StaticModInt<TMod>Inv(long n){if(n==0)throw new
    DivideByZeroException();if(fact.Length<=n)Resize(n);return inv[n];}[MethodImpl(256)]public StaticModInt<TMod>Binom(long n,long k){if(n<0)return 0
    ;if(n==0)return k==0?1:0;if(k<0||n<k)return 0;if(fact.Length<=n)Resize(n);return fact[n]*factinv[k]*factinv[n-k];}[MethodImpl(256)]public
    StaticModInt<TMod>BinomInv(long n,long k){if(n<0)throw new DivideByZeroException();if(0<=k&&k<=n){if(fact.Length<=n)Resize(n);return factinv[n]
    *fact[k]*fact[n-k];}throw new DivideByZeroException();}[MethodImpl(256)]public StaticModInt<TMod>Multinom(long n,long k1,long k2){if(n<0)return 0
    ;if(n==0)return k1==0&&k2==0?1:0;long k0=n-k1-k2;if(k0<0||k0>n)return 0;if(k1<0||k1>n)return 0;if(k2<0||k2>n)return 0;if(fact.Length<=n)Resize(n
    );return fact[n]*factinv[k0]*factinv[k1]*factinv[k2];}[MethodImpl(256)]public StaticModInt<TMod>Multinom(long n,params long[]ks){if(n<0)return 0
    ;long k0=n;foreach(var k in ks)k0-=k;if(k0<0||k0>n)return 0;if(fact.Length<=n)Resize(n);StaticModInt<TMod>ret=fact[n]*factinv[k0];for(int i=0;i<ks
    .Length;i++){long k=ks[i];if(k<0||k>n)return 0;ret*=factinv[k];}return ret;}}}
namespace Lib{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 StaticModInt<T>:IEquatable<StaticModInt<T>>,IField<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;public static StaticModInt<T>Zero=>default;public static
    StaticModInt<T>One=>new StaticModInt<T>(1u);[MethodImpl(256)]public static StaticModInt<T>Raw(int v){var u=unchecked((uint)v);return new
    StaticModInt<T>(u);}[MethodImpl(256)]public StaticModInt(long v):this(Round(v)){}[MethodImpl(256)]public StaticModInt(ulong v):this((uint)(v%op
    .Mod)){}[MethodImpl(256)]private StaticModInt(uint v)=>_v=v;public static bool IsZero(StaticModInt<T>x)=>x.Value==0;public static bool IsOne
    (StaticModInt<T>x)=>x.Value==1;[MethodImpl(256)]private static uint Round(long v){var x=v%op.Mod;if(x<0)x+=op.Mod;return(uint)x;}[MethodImpl(256
    )]public static StaticModInt<T>operator ++(StaticModInt<T>v){var x=v._v+1;if(x==op.Mod)x=0;return new StaticModInt<T>(x);}[MethodImpl(256)]public
    static StaticModInt<T>operator --(StaticModInt<T>v){var x=v._v;if(x==0)x=op.Mod;return new StaticModInt<T>(x-1);}[MethodImpl(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
    );}[MethodImpl(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);}}[MethodImpl(256)]public static StaticModInt<T>operator*(StaticModInt<T>lhs,StaticModInt<T>rhs)=>new
    StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));[MethodImpl(256)]public static StaticModInt<T>operator/(StaticModInt<T>lhs,StaticModInt<T>rhs
    )=>new StaticModInt<T>((uint)((ulong)lhs._v*Inv(rhs._v)%op.Mod));[MethodImpl(256)]public static StaticModInt<T>operator+(StaticModInt<T>v)=>v
    ;[MethodImpl(256)]public static StaticModInt<T>operator-(StaticModInt<T>v)=>new StaticModInt<T>(v._v==0?0:op.Mod-v._v);[MethodImpl(256)]public
    static bool operator==(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v==rhs._v;[MethodImpl(256)]public static bool operator!=(StaticModInt<T>lhs
    ,StaticModInt<T>rhs)=>lhs._v!=rhs._v;[MethodImpl(256)]public static implicit operator StaticModInt<T>(int v)=>new StaticModInt<T>(v);[MethodImpl
    (256)]public static implicit operator StaticModInt<T>(uint v)=>new StaticModInt<T>((long)v);[MethodImpl(256)]public static implicit operator
    StaticModInt<T>(long v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(ulong v)=>new StaticModInt<T>(v
    );[MethodImpl(256)]public static implicit operator long(StaticModInt<T>v)=>v._v;[MethodImpl(256)]public static implicit operator ulong
    (StaticModInt<T>v)=>v._v;[MethodImpl(256)]public StaticModInt<T>Pow(long n){var x=this;var r=new StaticModInt<T>(1U);if(n<0)(x,n)=(x.Inv(),-n
    );while(n>0){if((n&1)>0)r*=x;x*=x;n>>=1;}return r;}[MethodImpl(256)]public StaticModInt<T>Inv()=>new StaticModInt<T>(Inv(_v));[MethodImpl(256
    )]static ulong Inv(ulong x){long u=op.Mod,xu=1,yu=0,v=(long)x,xv=0,yv=1;while(v!=0){long w=SafeMod(u,v);long q=(u-w)/v;long xw=xu-xv*q;long yw=yu
    -yv*q;u=v;xu=xv;yu=yv;v=w;xv=xw;yv=yw;}return(ulong)(yu<0?yu+op.Mod:yu);}[MethodImpl(256)]static long SafeMod(long x,long m){long r=x%m;if(r<0)r
    +=m;return r;}[MethodImpl(256)]public override string ToString()=>_v.ToString();[MethodImpl(256)]public string ToString(string format
    ,IFormatProvider formatProvider)=>_v.ToString(format,formatProvider);[MethodImpl(256)]public override bool Equals(object?obj)=>obj is StaticModInt
    <T>m&&Equals(m);[MethodImpl(256)]public bool Equals(StaticModInt<T>other)=>_v==other._v;[MethodImpl(256)]public override int GetHashCode()=>_v
    .GetHashCode();}}
namespace Lib{public static class OutputLib{[MethodImpl(256)]public static void WriteJoin<T>(string s,IEnumerable<T>t)=>Console.WriteLine(string.Join
    (s,t));[MethodImpl(256)]public static void WriteMat<T>(T[,]a,string sep=" "){int sz1=a.GetLength(0),sz2=a.GetLength(1);var b=new T[sz2];for(int i
    =0;i<sz1;i++){for(int j=0;j<sz2;j++)b[j]=a[i,j];WriteJoin(sep,b);}}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,string sep=" "){foreach
    (var ar in a)WriteJoin(sep,ar);}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,Func<T,string>map,string sep=" "){foreach(var ar in a
    )WriteJoin(sep,ar.Select(x=>map(x)));}[MethodImpl(256)]public static void Write(object t)=>Console.WriteLine(t.ToString());[MethodImpl(256)]public
    static void Write(params object[]arg)=>Console.WriteLine(string.Join(" ",arg.Select(x=>x.ToString())));[MethodImpl(256)]public static void Write
    (string str)=>Console.WriteLine(str);[MethodImpl(256)]public static void WriteFlush(object t){Console.WriteLine(t.ToString());Console.Out.Flush
    ();}[MethodImpl(256)]public static void WriteError(object t)=>Console.Error.WriteLine(t.ToString());[MethodImpl(256)]public static void Flush
    ()=>Console.Out.Flush();[MethodImpl(256)]public static void YN(bool t)=>Console.WriteLine(t?"YES":"NO");[MethodImpl(256)]public static void Yn
    (bool t)=>Console.WriteLine(t?"Yes":"No");[MethodImpl(256)]public static void yn(bool t)=>Console.WriteLine(t?"yes":"no");[MethodImpl(256)]public
    static void DeleteLine()=>Console.Write("\x1b[1A\x1b[2K");[MethodImpl(256)]public static void ProgressBar(long now,long total,int blocks=50){int x
    =(int)((2*now*blocks+1)/(2*total));Console.Write($"\x1b[G[\x1b[42m{string.Concat(Enumerable.Repeat("_",x))}\x1b[0m{string.Concat(Enumerable.Repeat
    ("_",blocks-x))}] : {now} / {total}");}}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool
    ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0