using AtCoder.Internal; using ModInt = AtCoder.DynamicModInt; 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.Runtime.Intrinsics.X86; using System.Threading; namespace CpLibrary.Contest { public class SolverE : SolverBase { Scanner sr; bool HasMultipleTestcases { get; } ModInt[] factorial, finv; ModInt[] pow; public override void Solve() { var (n, mod) = sr.ReadValue(); ModInt.Mod = mod; Init(); var dp = CreateArray(n + 1, n + 1, (i, j) => new ModInt(0)); for (int i = 0; i < n + 1; i++) { dp[i][0] = 1; } for (int k = 2; k <= n; k++) { for (int i = n; i >= 0; i--) { for (int j = i - 1; j >= 0; j--) { ModInt multiplier = 1; for (int s = 1; s < 300; s++) { if (i - s * k < 0) break; if (j - s * (k - 1) < 0) break; multiplier *= Binom(i - (s - 1) * k, k); multiplier *= pow[k]; dp[i][j] += dp[i - s * k][j - s * (k - 1)] * multiplier * finv[s]; } } } } for (int i = 0; i < n; i++) { Console.WriteLine(dp[n][i]); } } public ModInt Binom(int n, int r) => factorial[n] * finv[r] * finv[n - r]; public void Init() { factorial = new ModInt[1000]; finv = new ModInt[1000]; factorial[0] = finv[0] = 1; for (int i = 1; i < 1000; i++) { factorial[i] = factorial[i - 1] * i; finv[i] = factorial[i].Inv(); } pow = CreateArray(301, i => new ModInt(i).Pow(i - 2)); pow[0] = pow[1] = 1; } public SolverE(Scanner sr) => this.sr = sr; public override void Run() { var _t = 1; if (HasMultipleTestcases) _t = sr.ReadInt(); while (_t-- > 0) Solve(); } public static T SignOutput(int x, T pos, T zero, T neg) => x == 0 ? zero : (x > 0 ? pos : neg); public static T[] CreateArray(int n, Func func) => Enumerable.Range(0, n).Select(p => func(p)).ToArray(); public static T[][] CreateArray(int h, int w, Func func) => Enumerable.Range(0, h).Select(i => Enumerable.Range(0, w).Select(j => func(i, j)).ToArray()).ToArray(); } public static class ProgramE { private static bool StartsOnThread = true; public static void Main(string[] args) { var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw); var sr = new Scanner(new StreamReader(Console.OpenStandardInput())); var solver = new SolverE(sr); if (StartsOnThread) { var thread = new Thread(new ThreadStart(() => solver.Run()), 1 << 27); thread.Start(); thread.Join(); } else solver.Run(); Console.Out.Flush(); } public static void Expand() => SourceExpander.Expander.Expand(); } } #region Expanded by https://github.com/naminodarie/SourceExpander namespace AtCoder{using static MethodImplOptions;public interface IDynamicModID{}public static class DynamicModIDExtension{public static void SetMod(this T _,int mod)where T:struct,IDynamicModID=>DynamicModInt.Mod=mod;}public readonly struct ModID0:IDynamicModID{}public readonly struct ModID1:IDynamicModID{}public readonly struct ModID2:IDynamicModID{}public readonly struct DynamicModIntOperator:IArithmeticOperator>where T:struct,IDynamicModID{public DynamicModIntMultiplyIdentity=>DynamicModInt.Raw(1);[MethodImpl(AggressiveInlining)]public DynamicModIntAdd(DynamicModIntx,DynamicModInty)=>x+y;[MethodImpl(AggressiveInlining)]public DynamicModIntSubtract(DynamicModIntx,DynamicModInty)=>x-y;[MethodImpl(AggressiveInlining)]public DynamicModIntMultiply(DynamicModIntx,DynamicModInty)=>x*y;[MethodImpl(AggressiveInlining)]public DynamicModIntDivide(DynamicModIntx,DynamicModInty)=>x/y;[MethodImpl(AggressiveInlining)]public DynamicModIntModulo(DynamicModIntx,DynamicModInty)=>throw new NotSupportedException();[MethodImpl(AggressiveInlining)]public DynamicModIntMinus(DynamicModIntx)=>-x;[MethodImpl(AggressiveInlining)]public DynamicModIntIncrement(DynamicModIntx)=> ++x;[MethodImpl(AggressiveInlining)]public DynamicModIntDecrement(DynamicModIntx)=> --x;}public readonly struct DynamicModInt:IEquatable>where T:struct,IDynamicModID{internal readonly uint _v;internal static Internal.Barrett bt;public int Value=>(int)_v;public static int Mod{get=>(int)bt.Mod;set{bt=new Internal.Barrett((uint)value);}}[MethodImpl(AggressiveInlining)]public static DynamicModIntRaw(int v){var u=unchecked((uint)v);return new DynamicModInt(u);}public DynamicModInt(long v):this(Round(v)){}private DynamicModInt(uint v)=>_v=v;[MethodImpl(AggressiveInlining)]private static uint Round(long v){var x=v%bt.Mod;if(x<0){x+=bt.Mod;}return(uint)x;}[MethodImpl(AggressiveInlining)]public static DynamicModIntoperator ++(DynamicModIntvalue){var v=value._v+1;if(v==bt.Mod){v=0;}return new DynamicModInt(v);}[MethodImpl(AggressiveInlining)]public static DynamicModIntoperator --(DynamicModIntvalue){var v=value._v;if(v==0){v=bt.Mod;}return new DynamicModInt(v-1);}[MethodImpl(AggressiveInlining)]public static DynamicModIntoperator+(DynamicModIntlhs,DynamicModIntrhs){var v=lhs._v+rhs._v;if(v>=bt.Mod){v-=bt.Mod;}return new DynamicModInt(v);}[MethodImpl(AggressiveInlining)]public static DynamicModIntoperator-(DynamicModIntlhs,DynamicModIntrhs){unchecked{var v=lhs._v-rhs._v;if(v>=bt.Mod){v+=bt.Mod;}return new DynamicModInt(v);}}[MethodImpl(AggressiveInlining)]public static DynamicModIntoperator*(DynamicModIntlhs,DynamicModIntrhs){uint z=bt.Mul(lhs._v,rhs._v);return new DynamicModInt(z);}public static DynamicModIntoperator/(DynamicModIntlhs,DynamicModIntrhs)=>lhs*rhs.Inv();public static DynamicModIntoperator+(DynamicModIntvalue)=>value;public static DynamicModIntoperator-(DynamicModIntvalue)=>new DynamicModInt(Mod-value.Value);public static bool operator==(DynamicModIntlhs,DynamicModIntrhs)=>lhs._v==rhs._v;public static bool operator!=(DynamicModIntlhs,DynamicModIntrhs)=>lhs._v!=rhs._v;public static implicit operator DynamicModInt(int value)=>new DynamicModInt(value);public static implicit operator DynamicModInt(long value)=>new DynamicModInt(value);public DynamicModIntPow(long n){var x=this;var r=Raw(1);while(n>0){if((n&1)>0){r*=x;}x*=x;n>>=1;}return r;}[MethodImpl(AggressiveInlining)]public DynamicModIntInv(){var(g,x)=Internal.InternalMath.InvGCD(_v,bt.Mod);return new DynamicModInt(x);}public override string ToString()=>_v.ToString();public override bool Equals(object obj)=>obj is DynamicModIntm&&Equals(m);public bool Equals(DynamicModIntother)=>Value==other.Value;public override int GetHashCode()=>_v.GetHashCode();}} namespace CpLibrary { public class Scanner { public StreamReader sr { get; private set; } string[] str; int index; char[] separators; public Scanner(StreamReader sr, char[] separators) { this.sr = sr; this.separators = separators; str = new string[0]; index = 0; } public Scanner(StreamReader sr): this(sr, new char[]{' '}) { } public Scanner(): this(new StreamReader(Console.OpenStandardInput()), new char[]{' '}) { } public string Read() { if (index < str.Length) return str[index++]; string s; do s = sr.ReadLine(); while (s == ""); str = s.Split(separators, StringSplitOptions.RemoveEmptyEntries); index = 0; return str[index++]; } public string ReadString() => Read(); public string[] ReadStringArray(int n) { var arr = new string[n]; for (int i = 0; i < n; i++) { arr[i] = ReadString(); } return arr; } public int ReadInt() => int.Parse(ReadString()); public int[] ReadIntArray(int n) => ReadValueArray(n); public long ReadLong() => long.Parse(ReadString()); public long[] ReadLongArray(int n) => ReadValueArray(n); public double ReadDouble() => double.Parse(ReadString()); public double[] ReadDoubleArray(int n) => ReadValueArray(n); public BigInteger ReadBigInteger() => BigInteger.Parse(ReadString()); public T1 ReadValue() => (T1)Convert.ChangeType(ReadString(), typeof(T1)); public T1[] ReadValueArray(int n) { var arr = new T1[n]; for (int i = 0; i < n; i++) { arr[i] = ReadValue(); } return arr; } public (T1, T2) ReadValue() => (ReadValue(), ReadValue()); public (T1, T2, T3) ReadValue() => (ReadValue(), ReadValue(), ReadValue()); public (T1, T2, T3, T4) ReadValue() => (ReadValue(), ReadValue(), ReadValue(), ReadValue()); public (T1, T2, T3, T4, T5) ReadValue() => (ReadValue(), ReadValue(), ReadValue(), ReadValue(), ReadValue()); public (T1, T2, T3, T4, T5, T6) ReadValue() => (ReadValue(), ReadValue(), ReadValue(), ReadValue(), ReadValue(), ReadValue()); public (T1, T2, T3, T4, T5, T6, T7) ReadValue() => (ReadValue(), ReadValue(), ReadValue(), ReadValue(), ReadValue(), ReadValue(), ReadValue()); public (T1[], T2[]) ReadValueArray(int n) { var(v1, v2) = (new T1[n], new T2[n]); for (int i = 0; i < n; i++) { (v1[i], v2[i]) = ReadValue(); } return (v1, v2); } public (T1[], T2[], T3[]) ReadValueArray(int n) { var(v1, v2, v3) = (new T1[n], new T2[n], new T3[n]); for (int i = 0; i < n; i++) { (v1[i], v2[i], v3[i]) = ReadValue(); } return (v1, v2, v3); } public (T1[], T2[], T3[], T4[]) ReadValueArray(int n) { var(v1, v2, v3, v4) = (new T1[n], new T2[n], new T3[n], new T4[n]); for (int i = 0; i < n; i++) { (v1[i], v2[i], v3[i], v4[i]) = ReadValue(); } return (v1, v2, v3, v4); } public (T1[], T2[], T3[], T4[], T5[]) ReadValueArray(int n) { var(v1, v2, v3, v4, v5) = (new T1[n], new T2[n], new T3[n], new T4[n], new T5[n]); for (int i = 0; i < n; i++) { (v1[i], v2[i], v3[i], v4[i], v5[i]) = ReadValue(); } return (v1, v2, v3, v4, v5); } public (T1[], T2[], T3[], T4[], T5[], T6[]) ReadValueArray(int n) { var(v1, v2, v3, v4, v5, v6) = (new T1[n], new T2[n], new T3[n], new T4[n], new T5[n], new T6[n]); for (int i = 0; i < n; i++) { (v1[i], v2[i], v3[i], v4[i], v5[i], v6[i]) = ReadValue(); } return (v1, v2, v3, v4, v5, v6); } public (T1[], T2[], T3[], T4[], T5[], T6[], T7[]) ReadValueArray(int n) { var(v1, v2, v3, v4, v5, v6, v7) = (new T1[n], new T2[n], new T3[n], new T4[n], new T5[n], new T6[n], new T7[n]); for (int i = 0; i < n; i++) { (v1[i], v2[i], v3[i], v4[i], v5[i], v6[i], v7[i]) = ReadValue(); } return (v1, v2, v3, v4, v5, v6, v7); } } } namespace CpLibrary { public interface ISolver { public void Solve(); public void Run(); } public abstract class SolverBase : ISolver { public abstract void Solve(); public abstract void Run(); public bool YesNo(bool condition) { Console.WriteLine(condition ? "Yes" : "No"); return condition; } public bool YESNO(bool condition) { Console.WriteLine(condition ? "YES" : "NO"); return condition; } public bool yesno(bool condition) { Console.WriteLine(condition ? "yes" : "no"); return condition; } } } 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 "";}}} namespace AtCoder{public interface IAdditionOperator{T Add(T x,T y);T Subtract(T x,T y);}public interface IMultiplicationOperator{T Multiply(T x,T y);T MultiplyIdentity{get;}}public interface IDivisionOperator:IMultiplicationOperator{T Divide(T x,T y);T Modulo(T x,T y);}public interface IUnaryNumOperator{T Minus(T x);T Increment(T x);T Decrement(T x);}public interface IArithmeticOperator:IAdditionOperator,IMultiplicationOperator,IDivisionOperator,IUnaryNumOperator{}public interface ICompareOperator:IComparer{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 INumOperator:IArithmeticOperator,ICompareOperator{T MinValue{get;}T MaxValue{get;}}public interface IShiftOperator{T LeftShift(T x,int y);T RightShift(T x,int y);}} namespace AtCoder.Internal{public class Barrett{public uint Mod{get;private set;}internal readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1;}public uint Mul(uint a,uint b){ulong z=a;z*=b;if(!Bmi2.X64.IsSupported)return(uint)(z%Mod);var x=Bmi2.X64.MultiplyNoFlags(z,IM);var v=unchecked((uint)(z-x*Mod));if(Mod<=v)v+=Mod;return v;}}} namespace AtCoder.Internal{public static partial class InternalMath{private static readonly DictionaryprimitiveRootsCache=new Dictionary(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};public static int PrimitiveRoot(int m){if(primitiveRootsCache.TryGetValue(m,out var p)){return p;}return primitiveRootsCache[m]=Calculate(m);int Calculate(int m){Spandivs=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;}for(int g=2;;g++){bool ok=true;for(int i=0;ibases=stackalloc long[3]{2,7,61};foreach(long a in bases){long t=d;long y=MathLib.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;}}} namespace AtCoder{public static class MathLib{public static int[]Convolution(int[]a,int[]b)=>Convolution(a,b);public static uint[]Convolution(uint[]a,uint[]b)=>Convolution(a,b);public static long[]Convolution(long[]a,long[]b)=>Convolution(a,b);public static ulong[]Convolution(ulong[]a,ulong[]b)=>Convolution(a,b);public static int[]Convolution(int[]a,int[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive(a.Select(ai=>new StaticModInt(ai)).ToArray(),b.Select(bi=>new StaticModInt(bi)).ToArray());return c.Select(ci=>ci.Value).ToArray();}else{int z=1<[z];for(int i=0;i(a[i]);}var bTemp=new StaticModInt[z];for(int i=0;i(b[i]);}var c=Convolution(aTemp,bTemp,n,m,z)[0..(n+m-1)];var result=new int[c.Length];for(int i=0;i(uint[]a,uint[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive(a.Select(ai=>new StaticModInt(ai)).ToArray(),b.Select(bi=>new StaticModInt(bi)).ToArray());return c.Select(ci=>(uint)ci.Value).ToArray();}else{int z=1<[z];for(int i=0;i(a[i]);}var bTemp=new StaticModInt[z];for(int i=0;i(b[i]);}var c=Convolution(aTemp,bTemp,n,m,z)[0..(n+m-1)];var result=new uint[c.Length];for(int i=0;i(long[]a,long[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive(a.Select(ai=>new StaticModInt(ai)).ToArray(),b.Select(bi=>new StaticModInt(bi)).ToArray());return c.Select(ci=>(long)ci.Value).ToArray();}else{int z=1<[z];for(int i=0;i(a[i]);}var bTemp=new StaticModInt[z];for(int i=0;i(b[i]);}var c=Convolution(aTemp,bTemp,n,m,z)[0..(n+m-1)];var result=new long[c.Length];for(int i=0;i(ulong[]a,ulong[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive(a.Select(TakeMod).ToArray(),b.Select(TakeMod).ToArray());return c.Select(ci=>(ulong)ci.Value).ToArray();}else{int z=1<[z];for(int i=0;i[z];for(int i=0;i(aTemp,bTemp,n,m,z)[0..(n+m-1)];var result=new ulong[c.Length];for(int i=0;iTakeMod(ulong x)=>StaticModInt.Raw((int)(x%default(TMod).Mod));}public static StaticModInt[]Convolution(StaticModInt[]a,StaticModInt[]b)where TMod:struct,IStaticMod{var temp=Convolution((ReadOnlySpan>)a,b);return temp.ToArray();}public static Span>Convolution(ReadOnlySpan>a,ReadOnlySpan>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty>();}if(Math.Min(n,m)<=60){return ConvolutionNaive(a,b);}int z=1<[z];a.CopyTo(aTemp);var bTemp=new StaticModInt[z];b.CopyTo(bTemp);return Convolution(aTemp.AsSpan(),bTemp.AsSpan(),n,m,z);}private static Span>Convolution(Span>a,Span>b,int n,int m,int z)where TMod:struct,IStaticMod{Internal.Butterfly.Calculate(a);Internal.Butterfly.Calculate(b);for(int i=0;i.CalculateInv(a);var result=a[0..(n+m-1)];var iz=new StaticModInt(z).Inv();foreach(ref var r in result){r*=iz;}return result;}public static long[]ConvolutionLong(ReadOnlySpana,ReadOnlySpanb){unchecked{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty();}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;ulong i1=(ulong)InternalMath.InvGCD((long)M2M3,(long)Mod1).Item2;ulong i2=(ulong)InternalMath.InvGCD((long)M1M3,(long)Mod2).Item2;ulong i3=(ulong)InternalMath.InvGCD((long)M1M2,(long)Mod3).Item2;var c1=Convolution(a,b);var c2=Convolution(a,b);var c3=Convolution(a,b);var c=new long[n+m-1];Spanoffset=stackalloc ulong[]{0,0,M1M2M3,2*M1M2M3,3*M1M2M3};for(int i=0;i(ReadOnlySpana,ReadOnlySpanb)where TMod:struct,IStaticMod{int z=1<[z];for(int i=0;i(a[i]);}var bTemp=new StaticModInt[z];for(int i=0;i(b[i]);}var c=AtCoder.MathLib.Convolution(aTemp,bTemp,a.Length,b.Length,z);var result=new ulong[c.Length];for(int i=0;i[]ConvolutionNaive(ReadOnlySpan>a,ReadOnlySpan>b)where TMod:struct,IStaticMod{if(a.Length[a.Length+b.Length-1];for(int i=0;i754974721;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;}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>=1;}return r;}public static long InvMod(long x,long m){var(g,res)=InternalMath.InvGCD(x,m);return res;}public static(long,long)CRT(long[]r,long[]m){long r0=0,m0=1;for(int i=0;i=m){ans+=(n-1)*n*(a/m)/2;a%=m;}if(b>=m){ans+=n*(b/m);b%=m;}long yMax=(a*n+b)/m;long xMax=yMax*m-b;if(yMax==0)return ans;ans+=(n-(xMax+a-1)/a)*yMax;(n,m,a,b)=(yMax,a,m,(a-xMax%a)%a);}}}} namespace AtCoder{using static MethodImplOptions;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:IArithmeticOperator>where T:struct,IStaticMod{public StaticModIntMultiplyIdentity=>StaticModInt.Raw(1);[MethodImpl(AggressiveInlining)]public StaticModIntAdd(StaticModIntx,StaticModInty)=>x+y;[MethodImpl(AggressiveInlining)]public StaticModIntSubtract(StaticModIntx,StaticModInty)=>x-y;[MethodImpl(AggressiveInlining)]public StaticModIntMultiply(StaticModIntx,StaticModInty)=>x*y;[MethodImpl(AggressiveInlining)]public StaticModIntDivide(StaticModIntx,StaticModInty)=>x/y;[MethodImpl(AggressiveInlining)]public StaticModIntModulo(StaticModIntx,StaticModInty)=>throw new NotSupportedException();[MethodImpl(AggressiveInlining)]public StaticModIntMinus(StaticModIntx)=>-x;[MethodImpl(AggressiveInlining)]public StaticModIntIncrement(StaticModIntx)=> ++x;[MethodImpl(AggressiveInlining)]public StaticModIntDecrement(StaticModIntx)=> --x;}public readonly struct StaticModInt:IEquatable>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;[MethodImpl(AggressiveInlining)]public static StaticModIntRaw(int v){var u=unchecked((uint)v);return new StaticModInt(u);}public StaticModInt(long v):this(Round(v)){}private StaticModInt(uint v)=>_v=v;[MethodImpl(AggressiveInlining)]private static uint Round(long v){var x=v%op.Mod;if(x<0){x+=op.Mod;}return(uint)x;}[MethodImpl(AggressiveInlining)]public static StaticModIntoperator ++(StaticModIntvalue){var v=value._v+1;if(v==op.Mod){v=0;}return new StaticModInt(v);}[MethodImpl(AggressiveInlining)]public static StaticModIntoperator --(StaticModIntvalue){var v=value._v;if(v==0){v=op.Mod;}return new StaticModInt(v-1);}[MethodImpl(AggressiveInlining)]public static StaticModIntoperator+(StaticModIntlhs,StaticModIntrhs){var v=lhs._v+rhs._v;if(v>=op.Mod){v-=op.Mod;}return new StaticModInt(v);}[MethodImpl(AggressiveInlining)]public static StaticModIntoperator-(StaticModIntlhs,StaticModIntrhs){unchecked{var v=lhs._v-rhs._v;if(v>=op.Mod){v+=op.Mod;}return new StaticModInt(v);}}[MethodImpl(AggressiveInlining)]public static StaticModIntoperator*(StaticModIntlhs,StaticModIntrhs){return new StaticModInt((uint)((ulong)lhs._v*rhs._v%op.Mod));}public static StaticModIntoperator/(StaticModIntlhs,StaticModIntrhs)=>lhs*rhs.Inv();public static StaticModIntoperator+(StaticModIntvalue)=>value;public static StaticModIntoperator-(StaticModIntvalue)=>new StaticModInt(op.Mod-value._v);public static bool operator==(StaticModIntlhs,StaticModIntrhs)=>lhs._v==rhs._v;public static bool operator!=(StaticModIntlhs,StaticModIntrhs)=>lhs._v!=rhs._v;public static implicit operator StaticModInt(int value)=>new StaticModInt(value);public static implicit operator StaticModInt(long value)=>new StaticModInt(value);public StaticModIntPow(long n){var x=this;var r=new StaticModInt(1U);while(n>0){if((n&1)>0){r*=x;}x*=x;n>>=1;}return r;}[MethodImpl(AggressiveInlining)]public StaticModIntInv(){if(op.IsPrime){return Pow(op.Mod-2);}else{var(g,x)=Internal.InternalMath.InvGCD(_v,op.Mod);return new StaticModInt(x);}}public override string ToString()=>_v.ToString();public override bool Equals(object obj)=>obj is StaticModIntm&&Equals(m);public bool Equals(StaticModIntother)=>_v==other._v;public override int GetHashCode()=>_v.GetHashCode();}} namespace AtCoder.Internal{public static class InternalBit{[MethodImpl(MethodImplOptions.AggressiveInlining)]public static int ExtractLowestSetBit(int n){if(Bmi1.IsSupported){return(int)Bmi1.ExtractLowestSetBit((uint)n);}return n&-n;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static int BSF(uint n){return BitOperations.TrailingZeroCount(n);}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 static class Butterflywhere T:struct,IStaticMod{internal static readonly StaticModInt[]sumE=CalcurateSumE();internal static readonly StaticModInt[]sumIE=CalcurateSumIE();[MethodImpl(MethodImplOptions.AggressiveOptimization)]public static void Calculate(Span>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector.Count;var modV=new Vector(default(T).Mod);for(int ph=1;ph<=h;ph++){int w=1<<(ph-1);int p=1<<(h-ph);var now=StaticModInt.Raw(1);for(int s=0;s,uint>(ls);var ru=MemoryMarshal.Cast,uint>(rs);for(int i=0;i(luSliced);var v=new Vector(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(MethodImplOptions.AggressiveOptimization)]public static void CalculateInv(Span>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector.Count;var modV=new Vector(default(T).Mod);for(int ph=h;ph>=1;ph--){int w=1<<(ph-1);int p=1<<(h-ph);var iNow=StaticModInt.Raw(1);for(int s=0;s.Raw((int)((ulong)(default(T).Mod+l.Value-r.Value)*(ulong)iNow.Value%default(T).Mod));}}else{var lu=MemoryMarshal.Cast,uint>(ls);var ru=MemoryMarshal.Cast,uint>(rs);for(int i=0;i(luSliced);var v=new Vector(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[]CalcurateSumE(){int g=InternalMath.PrimitiveRoot((int)default(T).Mod);int cnt2=InternalBit.BSF(default(T).Mod-1);var e=new StaticModInt(g).Pow((default(T).Mod-1)>>cnt2);var ie=e.Inv();var sumE=new StaticModInt[30];Span>es=stackalloc StaticModInt[cnt2-1];Span>ies=stackalloc StaticModInt[cnt2-1];for(int i=es.Length-1;i>=0;i--){es[i]=e;ies[i]=ie;e*=e;ie*=ie;}var now=StaticModInt.Raw(1);for(int i=0;i<=cnt2-2;i++){sumE[i]=es[i]*now;now*=ies[i];}return sumE;}private static StaticModInt[]CalcurateSumIE(){int g=InternalMath.PrimitiveRoot((int)default(T).Mod);int cnt2=InternalBit.BSF(default(T).Mod-1);var e=new StaticModInt(g).Pow((default(T).Mod-1)>>cnt2);var ie=e.Inv();var sumIE=new StaticModInt[30];Span>es=stackalloc StaticModInt[cnt2-1];Span>ies=stackalloc StaticModInt[cnt2-1];for(int i=es.Length-1;i>=0;i--){es[i]=e;ies[i]=ie;e*=e;ie*=ie;}var now=StaticModInt.Raw(1);for(int i=0;i<=cnt2-2;i++){sumIE[i]=ies[i]*now;now*=es[i];}return sumIE;}[Conditional("DEBUG")]private static void CheckPow2(int n){if(BitOperations.PopCount((uint)n)!=1){throw new ArgumentException("配列長は2のべき乗でなければなりません。");}}}} #endregion Expanded by https://github.com/naminodarie/SourceExpander