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/SourceExpander
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<T>:IArithmeticOperator<StaticModInt<T>>where T:struct,IStaticMod{public StaticModInt<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 new NotSupportedException();[MethodImpl(AggressiveInlining)]public StaticModInt<T>Minus(StaticModInt<T>x)=>-x;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Increment(StaticModInt<T>x)=> ++x;[MethodImpl(AggressiveInlining)]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;[MethodImpl(AggressiveInlining)]public static StaticModInt<T>Raw(int v){var u=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)]public static 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)]public static StaticModInt<T>operator*(StaticModInt<T>lhs,StaticModInt<T>rhs){return new StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));}public static 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)=>obj is 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(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<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], 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<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 { 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; }  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,bool ignoreAnyError=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);}public interface 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;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;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 static uint[]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)where TMod: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 static uint[]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(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 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=new long[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;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<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=stackalloc ulong[]{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 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;}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;}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 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.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(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 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 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[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 new ArgumentException("配列長は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