結果
| 問題 | No.1754 T-block Tiling |
| ユーザー |
 fairy_lettuce
|
| 提出日時 | 2021-11-20 13:12:43 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 52 ms / 2,000 ms |
| コード長 | 25,091 bytes |
| コンパイル時間 | 13,376 ms |
| コンパイル使用メモリ | 170,352 KB |
| 実行使用メモリ | 195,684 KB |
| 最終ジャッジ日時 | 2024-06-11 06:51:02 |
| 合計ジャッジ時間 | 14,061 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 1 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (100 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using AtCoder.Internal;using ModInt = AtCoder.StaticModInt<AtCoder.Mod998244353>;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 SolverB : SolverBase{Scanner sr;bool HasMultipleTestcases = true;public override void Solve(){var n = sr.ReadInt();var dp = CreateArray(n + 1, 2, (i, j) => new ModInt(0));dp[0][0] = 1;for (int i = 0; i < n; i++){dp[i + 1][0] = dp[i][0] * 2 + dp[i][1];dp[i + 1][1] = dp[i][0] * 2 + dp[i][1];}Console.WriteLine(dp[n][0]);}public SolverB(Scanner sr) => this.sr = sr;public override void Run(){var _t = 1;if (HasMultipleTestcases) _t = sr.ReadInt();while (_t-- > 0) Solve();}}public static class ProgramB{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 SolverB(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/SourceExpandernamespace 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<T>:IArithmeticOperator<StaticModInt<T>>where T:struct,IStaticMod{publicStaticModInt<T>MultiplyIdentity=>StaticModInt<T>.Raw(1);[MethodImpl(AggressiveInlining)]public StaticModInt<T>Add(StaticModInt<T>x,StaticModInt<T>y)=>x+y;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Subtract(StaticModInt<T>x,StaticModInt<T>y)=>x-y;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Multiply(StaticModInt<T>x,StaticModInt<T>y)=>x*y;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Divide(StaticModInt<T>x,StaticModInt<T>y)=>x/y;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Modulo(StaticModInt<T>x,StaticModInt<T>y)=>throw newNotSupportedException();[MethodImpl(AggressiveInlining)]public StaticModInt<T>Minus(StaticModInt<T>x)=>-x;[MethodImpl(AggressiveInlining)]publicStaticModInt<T>Increment(StaticModInt<T>x)=> ++x;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Decrement(StaticModInt<T>x)=> --x;}publicreadonly 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;[MethodImpl(AggressiveInlining)]public static StaticModInt<T>Raw(int v){varu=unchecked((uint)v);return new StaticModInt<T>(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)]publicstatic StaticModInt<T>operator ++(StaticModInt<T>value){var v=value._v+1;if(v==op.Mod){v=0;}return new StaticModInt<T>(v);}[MethodImpl(AggressiveInlining)]public static StaticModInt<T>operator --(StaticModInt<T>value){var v=value._v;if(v==0){v=op.Mod;}return new StaticModInt<T>(v-1);}[MethodImpl(AggressiveInlining)]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(AggressiveInlining)]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(AggressiveInlining)]publicstatic StaticModInt<T>operator*(StaticModInt<T>lhs,StaticModInt<T>rhs){return new StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));}publicstatic StaticModInt<T>operator/(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs*rhs.Inv();public static StaticModInt<T>operator+(StaticModInt<T>value)=>value;public static StaticModInt<T>operator-(StaticModInt<T>value)=>new StaticModInt<T>(op.Mod-value._v);public static bool operator==(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v==rhs._v;public static bool operator!=(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v!=rhs._v;public static implicit operator StaticModInt<T>(int value)=>new StaticModInt<T>(value);public static implicit operator StaticModInt<T>(long value)=>new StaticModInt<T>(value);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;}[MethodImpl(AggressiveInlining)]public StaticModInt<T>Inv(){if(op.IsPrime){return Pow(op.Mod-2);}else{var(g,x)=Internal.InternalMath.InvGCD(_v,op.Mod);return new StaticModInt<T>(x);}}public override string ToString()=>_v.ToString();public override bool Equals(object obj)=>objis StaticModInt<T>m&&Equals(m);public bool Equals(StaticModInt<T>other)=>_v==other._v;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(StreamReadersr): 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()); publicint[] ReadIntArray(int n) => ReadValueArray<int>(n); public long ReadLong() => long.Parse(ReadString()); public long[] ReadLongArray(int n) =>ReadValueArray<long>(n); public double ReadDouble() => double.Parse(ReadString()); public double[] ReadDoubleArray(int n) => ReadValueArray<double>(n); public BigInteger ReadBigInteger() => BigInteger.Parse(ReadString()); public T1 ReadValue<T1>() => (T1)Convert.ChangeType(ReadString(),typeof(T1)); public T1[] ReadValueArray<T1>(int n) { var arr = new T1[n]; for (int i = 0; i < n; i++) { arr[i] = ReadValue<T1>(); } return arr; }public (T1, T2) ReadValue<T1, T2>() => (ReadValue<T1>(), ReadValue<T2>()); public (T1, T2, T3) ReadValue<T1, T2, T3>() => (ReadValue<T1>(),ReadValue<T2>(), ReadValue<T3>()); public (T1, T2, T3, T4) ReadValue<T1, T2, T3, T4>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(),ReadValue<T4>()); public (T1, T2, T3, T4, T5) ReadValue<T1, T2, T3, T4, T5>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(), ReadValue<T4>(), ReadValue<T5>()); public (T1, T2, T3, T4, T5, T6) ReadValue<T1, T2, T3, T4, T5, T6>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(),ReadValue<T4>(), ReadValue<T5>(), ReadValue<T6>()); public (T1, T2, T3, T4, T5, T6, T7) ReadValue<T1, T2, T3, T4, T5, T6, T7>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(), ReadValue<T4>(), ReadValue<T5>(), ReadValue<T6>(), ReadValue<T7>()); public (T1[], T2[]) ReadValueArray<T1,T2>(int n) { var(v1, v2) = (new T1[n], new T2[n]); for (int i = 0; i < n; i++) { (v1[i], v2[i]) = ReadValue<T1, T2>(); } return (v1, v2); }public (T1[], T2[], T3[]) ReadValueArray<T1, T2, T3>(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<T1, T2, T3>(); } return (v1, v2, v3); } public (T1[], T2[], T3[], T4[]) ReadValueArray<T1, T2, T3, T4>(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<T1,T2, T3, T4>(); } return (v1, v2, v3, v4); } public (T1[], T2[], T3[], T4[], T5[]) ReadValueArray<T1, T2, T3, T4, T5>(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<T1,T2, T3, T4, T5>(); } return (v1, v2, v3, v4, v5); } public (T1[], T2[], T3[], T4[], T5[], T6[]) ReadValueArray<T1, T2, T3, T4, T5, T6>(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<T1, T2, T3, T4, T5, T6>(); } return (v1, v2, v3, v4, v5, v6); } public (T1[], T2[], T3[], T4[], T5[],T6[], T7[]) ReadValueArray<T1, T2, T3, T4, T5, T6, T7>(int n) { var(v1, v2, v3, v4, v5, v6, v7) = (new T1[n], new T2[n], new T3[n], new T4[n], newT5[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<T1, T2, T3, T4, T5, T6,T7>(); } return (v1, v2, v3, v4, v5, v6, v7); } } }namespace CpLibrary { public interface ISolver { public void Solve(); public void Run(); } public abstract class SolverBase : ISolver { publicabstract void Solve(); public abstract void Run(); public bool YesNo(bool condition) { Console.WriteLine(condition ? "Yes" : "No"); returncondition; } public bool YESNO(bool condition) { Console.WriteLine(condition ? "YES" : "NO"); return condition; } public bool yesno(boolcondition) { Console.WriteLine(condition ? "yes" : "no"); return condition; } public static T SignOutput<T>(int x, T pos, T zero, T neg) => x ==0 ? zero : (x > 0 ? pos : neg); public static T[] CreateArray<T>(int n, Func<int, T> func) => Enumerable.Range(0, n).Select(p => func(p)).ToArray(); public static T[][] CreateArray<T>(int h, int w, Func<int, int, T> func) => Enumerable.Range(0, h).Select(i => Enumerable.Range(0, w).Select(j=> func(i, j)).ToArray()).ToArray(); } }namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,boolignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}namespace AtCoder{public interface IAdditionOperator<T>{T Add(T x,T y);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);}publicinterface IUnaryNumOperator<T>{T Minus(T x);T Increment(T x);T Decrement(T x);}public interface IArithmeticOperator<T>:IAdditionOperator<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 INumOperator<T>:IArithmeticOperator<T>,ICompareOperator<T>{T MinValue{get;}T MaxValue{get;}}public interface IShiftOperator<T>{T LeftShift(T x,int y);T RightShift(T x,int y);}}namespace AtCoder.Internal{public static partial class InternalMath{private static readonly Dictionary<int,int>primitiveRootsCache=new Dictionary<int,int>(){{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){Span<int>divs=stackalloc int[20];divs[0]=2;int cnt=1;intx=(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;i<cnt;i++){if(MathLib.PowMod(g,(m-1)/divs[i],m)==1){ok=false;break;}}if(ok){return g;}}}}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;}}public static long SafeMod(long x,long m){x%=m;if(x<0)x+=m;return x;}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<long>bases=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<Mod998244353>(a,b);public staticuint[]Convolution(uint[]a,uint[]b)=>Convolution<Mod998244353>(a,b);public static long[]Convolution(long[]a,long[]b)=>Convolution<Mod998244353>(a,b);public static ulong[]Convolution(ulong[]a,ulong[]b)=>Convolution<Mod998244353>(a,b);public static int[]Convolution<TMod>(int[]a,int[]b)whereTMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<int>();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive<TMod>(a.Select(ai=>new StaticModInt<TMod>(ai)).ToArray(),b.Select(bi=>new StaticModInt<TMod>(bi)).ToArray());return c.Select(ci=>ci.Value).ToArray();}else{int z=1<<InternalBit.CeilPow2(n+m-1);var aTemp=new StaticModInt<TMod>[z];for(int i=0;i<a.Length;i++){aTemp[i]=new StaticModInt<TMod>(a[i]);}var bTemp=new StaticModInt<TMod>[z];for(int i=0;i<b.Length;i++){bTemp[i]=new StaticModInt<TMod>(b[i]);}var c=Convolution<TMod>(aTemp,bTemp,n,m,z)[0..(n+m-1)];var result=new int[c.Length];for(int i=0;i<result.Length;i++){result[i]=c[i].Value;}return result;}}public staticuint[]Convolution<TMod>(uint[]a,uint[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<uint>();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive<TMod>(a.Select(ai=>new StaticModInt<TMod>(ai)).ToArray(),b.Select(bi=>new StaticModInt<TMod>(bi)).ToArray());return c.Select(ci=>(uint)ci.Value).ToArray();}else{int z=1<<InternalBit.CeilPow2(n+m-1);var aTemp=new StaticModInt<TMod>[z];for(inti=0;i<a.Length;i++){aTemp[i]=new StaticModInt<TMod>(a[i]);}var bTemp=new StaticModInt<TMod>[z];for(int i=0;i<b.Length;i++){bTemp[i]=newStaticModInt<TMod>(b[i]);}var c=Convolution<TMod>(aTemp,bTemp,n,m,z)[0..(n+m-1)];var result=new uint[c.Length];for(int i=0;i<result.Length;i++){result[i]=(uint)c[i].Value;}return result;}}public static long[]Convolution<TMod>(long[]a,long[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<long>();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive<TMod>(a.Select(ai=>new StaticModInt<TMod>(ai)).ToArray(),b.Select(bi=>new StaticModInt<TMod>(bi)).ToArray());return c.Select(ci=>(long)ci.Value).ToArray();}else{int z=1<<InternalBit.CeilPow2(n+m-1);var aTemp=new StaticModInt<TMod>[z];for(int i=0;i<a.Length;i++){aTemp[i]=new StaticModInt<TMod>(a[i]);}var bTemp=new StaticModInt<TMod>[z];for(int i=0;i<b.Length;i++){bTemp[i]=new StaticModInt<TMod>(b[i]);}var c=Convolution<TMod>(aTemp,bTemp,n,m,z)[0..(n+m-1)];var result=newlong[c.Length];for(int i=0;i<result.Length;i++){result[i]=c[i].Value;}return result;}}public static ulong[]Convolution<TMod>(ulong[]a,ulong[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<ulong>();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive<TMod>(a.Select(TakeMod).ToArray(),b.Select(TakeMod).ToArray());return c.Select(ci=>(ulong)ci.Value).ToArray();}else{int z=1<<InternalBit.CeilPow2(n+m-1);var aTemp=new StaticModInt<TMod>[z];for(int i=0;i<a.Length;i++){aTemp[i]=TakeMod(a[i]);}var bTemp=new StaticModInt<TMod>[z];for(int i=0;i<b.Length;i++){bTemp[i]=TakeMod(b[i]);}var c=Convolution<TMod>(aTemp,bTemp,n,m,z)[0..(n+m-1)];var result=new ulong[c.Length];for(int i=0;i<result.Length;i++){result[i]=(ulong)c[i].Value;}return result;}static StaticModInt<TMod>TakeMod(ulong x)=>StaticModInt<TMod>.Raw((int)(x%default(TMod).Mod));}public static StaticModInt<TMod>[]Convolution<TMod>(StaticModInt<TMod>[]a,StaticModInt<TMod>[]b)where TMod:struct,IStaticMod{var temp=Convolution((ReadOnlySpan<StaticModInt<TMod>>)a,b);return temp.ToArray();}public static Span<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);}int z=1<<InternalBit.CeilPow2(n+m-1);var aTemp=new StaticModInt<TMod>[z];a.CopyTo(aTemp);var bTemp=new StaticModInt<TMod>[z];b.CopyTo(bTemp);return Convolution(aTemp.AsSpan(),bTemp.AsSpan(),n,m,z);}private static Span<StaticModInt<TMod>>Convolution<TMod>(Span<StaticModInt<TMod>>a,Span<StaticModInt<TMod>>b,int n,int m,int z)where TMod:struct,IStaticMod{Internal.Butterfly<TMod>.Calculate(a);Internal.Butterfly<TMod>.Calculate(b);for(int i=0;i<a.Length;i++){a[i]*=b[i];}Internal.Butterfly<TMod>.CalculateInv(a);var result=a[0..(n+m-1)];var iz=new StaticModInt<TMod>(z).Inv();foreach(ref var r in result){r*=iz;}return result;}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;constulong 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<FFTMod1>(a,b);var c2=Convolution<FFTMod2>(a,b);var c3=Convolution<FFTMod3>(a,b);var c=new long[n+m-1];Span<ulong>offset=stackalloculong[]{0,0,M1M2M3,2*M1M2M3,3*M1M2M3};for(int i=0;i<c.Length;i++){ulong x=0;x+=(c1[i]*i1)%Mod1*M2M3;x+=(c2[i]*i2)%Mod2*M1M3;x+=(c3[i]*i3)%Mod3*M1M2;long diff=(long)c1[i]-InternalMath.SafeMod((long)x,(long)Mod1);if(diff<0){diff+=(long)Mod1;}x-=offset[(int)(diff%offset.Length)];c[i]=(long)x;}return c;}}private static ulong[]Convolution<TMod>(ReadOnlySpan<long>a,ReadOnlySpan<long>b)where TMod:struct,IStaticMod{int z=1<<InternalBit.CeilPow2(a.Length+b.Length-1);var aTemp=new StaticModInt<TMod>[z];for(int i=0;i<a.Length;i++){aTemp[i]=new StaticModInt<TMod>(a[i]);}var bTemp=new StaticModInt<TMod>[z];for(int i=0;i<b.Length;i++){bTemp[i]=new StaticModInt<TMod>(b[i]);}var c=AtCoder.MathLib.Convolution<TMod>(aTemp,bTemp,a.Length,b.Length,z);var result=new ulong[c.Length];for(int i=0;i<result.Length;i++){result[i]=(ulong)c[i].Value;}return result;}private staticStaticModInt<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;}private readonly struct FFTMod1:IStaticMod{public uint Mod=>754974721;public bool IsPrime=>true;}privatereadonly struct FFTMod2:IStaticMod{public uint Mod=>167772161;public bool IsPrime=>true;}private readonly struct FFTMod3:IStaticMod{public uintMod=>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<n){if((n&1)!=0)r=barrett.Mul(r,y);y=barrett.Mul(y,y);n>>=1;}return r;}public static longInvMod(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.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);}public static long FloorSum(long n,long m,long a,long b){long ans=0;while(true){if(a>=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.Internal{public static class InternalBit{[MethodImpl(MethodImplOptions.AggressiveInlining)]public static int ExtractLowestSetBit(intn){if(Bmi1.IsSupported){return(int)Bmi1.ExtractLowestSetBit((uint)n);}return n&-n;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public staticint 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 Butterfly<T>where T:struct,IStaticMod{internal static readonly StaticModInt<T>[]sumE=CalcurateSumE();internal static readonly StaticModInt<T>[]sumIE=CalcurateSumIE();[MethodImpl(MethodImplOptions.AggressiveOptimization)]public static voidCalculate(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);varls=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[i..];var ruSliced=ru[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(MethodImplOptions.AggressiveOptimization)]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[i..];var ruSliced=ru[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((int)default(T).Mod);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((int)default(T).Mod);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("DEBUG")]private static void CheckPow2(int n){if(BitOperations.PopCount((uint)n)!=1){throw newArgumentException("配列長は2のべき乗でなければなりません。");}}}}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;}}}#endregion Expanded by https://github.com/naminodarie/SourceExpander