using Lib; using Lib.MathLib; using ModInt = Lib.StaticModInt; 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.Functions; using static Lib.OutputLib; public class Solver { const bool MultiTestCase = false; void Solve() { int n = ri, h = ri; var inv2 = ((ModInt)2).Inv(); var inv3 = ((ModInt)3).Inv(); var a = new ModInt[3, 3]; a[0, 0] = inv2; a[0, 1] = inv2; a[1, 0] = inv3; a[1, 1] = inv3; a[1, 2] = inv3; a[2, 1] = inv3 * 2; a[2, 2] = inv3; var b = new int[] { 0, 1, 1 }; var x = new ModInt[9][]; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { x[3 * i + j] = new ModInt[b[j] + 1]; x[3 * i + j][b[j]] = a[i, j]; } var inv5 = ((ModInt)5).Inv(); var y = new ModInt[3][]; for (int i = 0; i < 3; i++) { y[i] = new ModInt[b[i] + 1]; y[i][b[i]] = inv5 * (i <= 1 ? 2 : 1); } ModInt[][] Mul(ModInt[][] a, ModInt[][] b) { var c = new ModInt[9][]; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { int l = 0; for (int k = 0; k < 3; k++) Chmax(ref l, a[3 * i + k].Length + b[3 * k + j].Length - 1); var f = new ModInt[l]; for (int k = 0; k < 3; k++) { var g = Convolution.Calc(a[3 * i + k], b[3 * k + j]); for (int h = 0; h < g.Length; h++) f[h] += g[h]; } c[3 * i + j] = f; } return c; } n--; while (n > 0) { if (n % 2 == 1) { var z = new ModInt[3][]; for (int k = 0; k < 3; k++) { int l = 0; for (int i = 0; i < 3; i++) Chmax(ref l, y[i].Length + x[3 * i + k].Length - 1); var f = new ModInt[l]; for (int i = 0; i < 3; i++) { var g = Convolution.Calc(y[i], x[3 * i + k]); for (int j = 0; j < g.Length; j++) f[j] += g[j]; } z[k] = f; } y = z; } x = Mul(x, x); n /= 2; } ModInt ans = 0; for (int i = 0; i < 3; i++) { var f = y[i]; for (int k = h; k < f.Length; k++) ans += f[k]; } Write(ans); } #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(out T[] a, int n, Func read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(); } void ReadArray(out T[] a, int n, Func 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{public static class Functions{[MethodImpl(256)]public static int Popcount(ulong x){x=(x&0x5555555555555555UL)+((x>>1)&0x5555555555555555UL);x=(x&0x3333333333333333UL)+((x>>2)&0x3333333333333333UL);x=(x&0x0f0f0f0f0f0f0f0fUL)+((x>>4)&0x0f0f0f0f0f0f0f0fUL);x=(x&0x00ff00ff00ff00ffUL)+((x>>8)&0x00ff00ff00ff00ffUL);x=(x&0x0000ffff0000ffffUL)+((x>>16)&0x0000ffff0000ffffUL);x=(x&0x00000000ffffffffUL)+((x>>32)&0x00000000ffffffffUL);return(int)x;}[MethodImpl(256)]public static int Popcount(long x){x=(x&0x5555555555555555L)+((x>>1)&0x5555555555555555L);x=(x&0x3333333333333333L)+((x>>2)&0x3333333333333333L);x=(x&0x0f0f0f0f0f0f0f0fL)+((x>>4)&0x0f0f0f0f0f0f0f0fL);x=(x&0x00ff00ff00ff00ffL)+((x>>8)&0x00ff00ff00ff00ffL);x=(x&0x0000ffff0000ffffL)+((x>>16)&0x0000ffff0000ffffL);x=(x&0x00000000ffffffffL)+((x>>32)&0x00000000ffffffffL);return(int)x;}[MethodImpl(256)]public static int Popcount(int x){x=(x&0x55555555)+((x>>1)&0x55555555);x=(x&0x33333333)+((x>>2)&0x33333333);x=(x&0x0f0f0f0f)+((x>>4)&0x0f0f0f0f);x=(x&0x00ff00ff)+((x>>8)&0x00ff00ff);x=(x&0x0000ffff)+((x>>16)&0x0000ffff);return x;}[MethodImpl(256)]public static int Ctz(long x){if(x==0)return-1;return Popcount((ulong)((x&-x)-1));}[MethodImpl(256)]public static int CeilPow2(int n){int x=0;while((1<a<=b&&b<=c;[MethodImpl(256)]public static int Sign(long x)=>x==0?0:(x<0?-1:1);[MethodImpl(256)]public static int Sign(double x)=>x==0?0:(x<0?-1:1);[MethodImpl(256)]public static int DigitSum(long n,int d=10){long s=0;while(n>0){s+=n%d;n/=d;}return(int)s;}[MethodImpl(256)]public static long Floor(long a,long b)=>a>=0?a/b:(a+1)/b-1;[MethodImpl(256)]public static long Ceil(long a,long b)=>a>0?(a-1)/b+1:a/b;[MethodImpl(256)]public static int Gcd(int a,int b)=>b==0?a:Gcd(b,a%b);[MethodImpl(256)]public static uint Gcd(uint a,uint b)=>b==0?a:Gcd(b,a%b);[MethodImpl(256)]public static long Gcd(long a,long b)=>b==0?a:Gcd(b,a%b);[MethodImpl(256)]public static ulong Gcd(ulong a,ulong b)=>b==0?a:Gcd(b,a%b);[MethodImpl(256)]public static(long x,long y,long g)ExtGcd(long a,long b){if(b==0)return(Sign(a),0,Math.Abs(a));long c=SafeMod(a,b);var(x2,y2,g)=ExtGcd(b,c);long x=SafeMod(y2,b);long y=(g-a*x)/b;return(x,y,g);}[MethodImpl(256)]public static void Swap(ref int x,ref int y){x^=y;y^=x;x^=y;}[MethodImpl(256)]public static void Swap(ref long x,ref long y){x^=y;y^=x;x^=y;}[MethodImpl(256)]public static void Swap(ref T x,ref T y){T t=y;y=x;x=t;}[MethodImpl(256)]public static T Clamp(T x,T l,T r)where T:IComparable =>x.CompareTo(l)<=0?l:(x.CompareTo(r)<=0?x:r);[MethodImpl(256)]public static T Clamp(ref T x,T l,T r)where T:IComparable =>x=x.CompareTo(l)<=0?l:(x.CompareTo(r)<=0?x:r);[MethodImpl(256)]public static void Chmin(ref T x,T y)where T:IComparable{if(x.CompareTo(y)>0)x=y;}[MethodImpl(256)]public static void Chmax(ref T x,T y)where T:IComparable{if(x.CompareTo(y)<0)x=y;}[MethodImpl(256)]public static int LowerBound(long[]arr,long val,int l=-1,int r=-1)=>LowerBound(arr.AsSpan(),t=>Sign(t-val),l,r);[MethodImpl(256)]public static int LowerBound(int[]arr,int val,int l=-1,int r=-1)=>LowerBound(arr.AsSpan(),t=>t-val,l,r);[MethodImpl(256)]public static int LowerBound(T[]arr,T val,int l=-1,int r=-1)where T:IComparable =>LowerBound(arr.AsSpan(),t=>t.CompareTo(val),l,r);[MethodImpl(256)]public static int LowerBound(T[]arr,Funccomp,int l=-1,int r=-1)=>LowerBound(arr.AsSpan(),comp,l,r);[MethodImpl(256)]public static int LowerBound(Spandata,Funccomp,int l=-1,int r=-1){if(data.Length==0)return-1;if(l==-1)l=0;if(r==-1)r=data.Length;while(l(T[]arr,T geq,T lt,int l=-1,int r=-1)where T:IComparable =>Math.Max(0,LowerBound(arr.AsSpan(),t=>t.CompareTo(lt),l,r)-LowerBound(arr.AsSpan(),t=>t.CompareTo(geq),l,r));[MethodImpl(256)]public static string ToBase2(long v,int digit=-1){if(digit==-1){digit=0;while((v>>digit)>0)digit++;}var c=new string[digit];for(int i=0;i>i)&1)==0?"0":"1";return string.Join("",c);}[MethodImpl(256)]public static string ToBaseN(long v,int n,int digit=-1){if(digit==-1){digit=0;long pow=1;while(v>=pow){digit++;pow*=n;}}var c=new int[digit];for(int i=0;i[n];for(int i=0;i();for(int i=0;i=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=0;do b=Read();while(b<33||126=33&&b<=126;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public long Integer(){long ret=0;byte b=0;var ng=false;do b=Read();while(b!='-'&&(b<'0'||'9'double.Parse(Scan());}} namespace Lib.MathLib{public static class Convolution{[MethodImpl(256)]public static uint[]Calc(ReadOnlySpana,ReadOnlySpanb)where TMod:struct,IStaticMod{var u=new StaticModInt[a.Length];for(int i=0;i[b.Length];for(int i=0;i(u,v);var r=new uint[u.Length];for(int i=0;i(ReadOnlySpana,ReadOnlySpanb)where TMod:struct,IStaticMod{var u=new StaticModInt[a.Length];for(int i=0;i[b.Length];for(int i=0;i(u,v);var r=new long[u.Length];for(int i=0;i[]Calc(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)<=30)return Naive(a,b);return FFT(a,b);}[MethodImpl(256)]public static StaticModInt[]Calc(StaticModInt[]a,StaticModInt[]b)where TMod:struct,IStaticMod=>Calc((ReadOnlySpan>)a,b);[MethodImpl(256)]public static StaticModInt[]Square(ReadOnlySpan>a)where TMod:struct,IStaticMod{var n=a.Length;if(n==0)return Array.Empty>();if(n<=30)return Naive(a,a);return SquareFFT(a);}[MethodImpl(256)]private static StaticModInt[]SquareFFT(ReadOnlySpan>a)where TMod:struct,IStaticMod{int n=a.Length;int z=1<[z];a.CopyTo(a2);Butterfly.Calculate(a2);for(int i=0;i.CalculateInv(a2);Array.Resize(ref a2,2*n-1);var iz=new StaticModInt(z).Inv();for(int i=0;i[]FFT(ReadOnlySpan>a,ReadOnlySpan>b)where TMod:struct,IStaticMod{int n=a.Length,m=b.Length;int z=1<[z];var b2=new StaticModInt[z];a.CopyTo(a2);b.CopyTo(b2);var result=FFTInner(a2,b2);Array.Resize(ref result,n+m-1);var iz=new StaticModInt(z).Inv();for(int i=0;i[]FFTInner(StaticModInt[]a,StaticModInt[]b)where TMod:struct,IStaticMod{Butterfly.Calculate(a);Butterfly.Calculate(b);for(int i=0;i.CalculateInv(a);return a;}[MethodImpl(256)]private static StaticModInt[]Naive(ReadOnlySpan>a,ReadOnlySpan>b)where TMod:struct,IStaticMod{if(a.Length[a.Length+b.Length-1];for(int i=0;ia,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;const ulong i1=190329765;const ulong i2=58587104;const ulong i3=187290749;var c1=Calc(a,b);var c2=Calc(a,b);var c3=Calc(a,b);var c=new long[n+m-1];for(int i=0;i[]IntMod(ReadOnlySpan>a,ReadOnlySpan>b)where Mod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0)return Array.Empty>();const long Mod1=754974721;const long Mod2=167772161;const long Mod3=469762049;const long M1invM2=95869806;const long M12invM3=187290749;int mod=StaticModInt.Mod;long M12mod=Mod1*Mod2%mod;var u=new long[n];for(int i=0;i(u,v);var c2=Calc(u,v);var c3=Calc(u,v);var c=new StaticModInt[n+m-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;}}} 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{public static uint Mod{get;private set;}public static uint[]sumE;public static uint[]sumIE;public static void SetMod(uint mod){Mod=mod;Montgomery.Init(mod);sumE=CalcurateSumE();sumIE=CalcurateSumIE();}[MethodImpl(256)]public static void Calculate(Spana){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector.Count;var modV=new Vector(Mod);for(int ph=1;ph<=h;ph++){int w=1<<(ph-1);int p=1<<(h-ph);uint now=1;for(int s=0;s=Mod)ls[i]-=Mod;rs[i]=l-r;if(rs[i]>=Mod)rs[i]+=Mod;}}else{foreach(ref var r in rs)r=Montgomery.Mul(r,now);for(int i=0;i(lsSliced);var v=new Vector(rsSliced);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(lsSliced);sub.CopyTo(rsSliced);}}now=Montgomery.Mul(now,sumE[InternalBit.Bsf(~(uint)s)]);}}}[MethodImpl(256)]public static void CalculateInv(Spana){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector.Count;var modV=new Vector(Mod);for(int ph=h;ph>=1;ph--){int w=1<<(ph-1);int p=1<<(h-ph);uint iNow=1;for(int s=0;s=Mod)ls[i]-=Mod;rs[i]=l-r;if(rs[i]>=Mod)rs[i]+=Mod;rs[i]=Montgomery.Mul(rs[i],iNow);}}else{for(int i=0;i(lsSliced);var v=new Vector(rsSliced);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(lsSliced);sub.CopyTo(rsSliced);}foreach(ref var r in rs)r=Montgomery.Mul(r,iNow);}iNow=Montgomery.Mul(iNow,sumIE[InternalBit.Bsf(~(uint)s)]);}}}public static uint[]CalcurateSumE(){uint g=(uint)InternalMath.PrimitiveRoot(Mod);int cnt2=InternalBit.Bsf(Mod-1);var e=Pow(g,(Mod-1)>>cnt2);var ie=Pow(e,Mod-2);var sumE=new uint[30];Spanes=stackalloc uint[cnt2-1];Spanies=stackalloc uint[cnt2-1];for(int i=es.Length-1;i>=0;i--){es[i]=e;ies[i]=ie;e=Montgomery.Mul(e,e);ie=Montgomery.Mul(ie,ie);}uint now=1;for(int i=0;i<=cnt2-2;i++){sumE[i]=Montgomery.Mul(es[i],now);now=Montgomery.Mul(now,ies[i]);}return sumE;}public static uint[]CalcurateSumIE(){uint g=(uint)InternalMath.PrimitiveRoot(Mod);int cnt2=InternalBit.Bsf(Mod-1);var e=Pow(g,(Mod-1)>>cnt2);var ie=Pow(e,Mod-2);var sumIE=new uint[30];Spanes=stackalloc uint[cnt2-1];Spanies=stackalloc uint[cnt2-1];for(int i=es.Length-1;i>=0;i--){es[i]=e;ies[i]=ie;e=Montgomery.Mul(e,e);ie=Montgomery.Mul(ie,ie);}uint now=1;for(int i=0;i<=cnt2-2;i++){sumIE[i]=Montgomery.Mul(ies[i],now);now=Montgomery.Mul(now,es[i]);}return sumIE;}static uint Pow(uint x,uint n){uint y=1;for(;n>0;n>>=1){if((n&1)==1)y=Montgomery.Mul(y,x);x=Montgomery.Mul(x,x);}return y;}[Conditional("ATCODER_CONTRACT")]private static void CheckPow2(int n){if(BitOperations.PopCount((uint)n)!=1){throw new ArgumentException("配列長は2のべき乗でなければなりません。");}}}public static class Butterflywhere T:struct,IStaticMod{public static readonly StaticModInt[]sumE=CalcurateSumE();public static readonly StaticModInt[]sumIE=CalcurateSumIE();public static readonly uint Mod=default(T).Mod;[MethodImpl(256)]public static void Calculate(Span>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector.Count;var modV=new Vector(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(256)]public static void CalculateInv(Span>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector.Count;var modV=new Vector(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)(Mod+l.Value-r.Value)*(ulong)iNow.Value%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)];}}}public static StaticModInt[]CalcurateSumE(){int g=InternalMath.PrimitiveRoot();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;}public static StaticModInt[]CalcurateSumIE(){int g=InternalMath.PrimitiveRoot();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("ATCODER_CONTRACT")]private static void CheckPow2(int n){if(BitOperations.PopCount((uint)n)!=1){throw new ArgumentException("配列長は2のべき乗でなければなりません。");}}}} namespace Lib{public static class InternalMath{private static readonly DictionaryprimitiveRootsCache=new Dictionary(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};[MethodImpl(256)]public static int PrimitiveRoot()where TMod:struct,IStaticMod{uint m=default(TMod).Mod;if(primitiveRootsCache.TryGetValue(m,out var p))return p;return primitiveRootsCache[m]=PrimitiveRootCalculate();}static int PrimitiveRootCalculate()where TMod:struct,IStaticMod{var m=default(TMod).Mod;Spandivs=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(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){Spandivs=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);uint Pow(uint x,uint n){uint 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;ReadOnlySpanbases=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>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{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: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;public static StaticModIntZero=>default;public static StaticModIntOne=>new StaticModInt(1u);[MethodImpl(256)]public static StaticModIntRaw(int v){var u=unchecked((uint)v);return new StaticModInt(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;[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 StaticModIntoperator ++(StaticModIntv){var x=v._v+1;if(x==op.Mod)x=0;return new StaticModInt(x);}[MethodImpl(256)]public static StaticModIntoperator --(StaticModIntv){var x=v._v;if(x==0)x=op.Mod;return new StaticModInt(x-1);}[MethodImpl(256)]public static StaticModIntoperator+(StaticModIntlhs,StaticModIntrhs){var v=lhs._v+rhs._v;if(v>=op.Mod)v-=op.Mod;return new StaticModInt(v);}[MethodImpl(256)]public static StaticModIntoperator-(StaticModIntlhs,StaticModIntrhs){unchecked{var v=lhs._v-rhs._v;if(v>=op.Mod)v+=op.Mod;return new StaticModInt(v);}}[MethodImpl(256)]public static StaticModIntoperator*(StaticModIntlhs,StaticModIntrhs)=>new StaticModInt((uint)((ulong)lhs._v*rhs._v%op.Mod));[MethodImpl(256)]public static StaticModIntoperator/(StaticModIntlhs,StaticModIntrhs)=>new StaticModInt((uint)((ulong)lhs._v*Inv(rhs._v)%op.Mod));[MethodImpl(256)]public static StaticModIntoperator+(StaticModIntv)=>v;[MethodImpl(256)]public static StaticModIntoperator-(StaticModIntv)=>new StaticModInt(v._v==0?0:op.Mod-v._v);[MethodImpl(256)]public static bool operator==(StaticModIntlhs,StaticModIntrhs)=>lhs._v==rhs._v;[MethodImpl(256)]public static bool operator!=(StaticModIntlhs,StaticModIntrhs)=>lhs._v!=rhs._v;[MethodImpl(256)]public static implicit operator StaticModInt(int v)=>new StaticModInt(v);[MethodImpl(256)]public static implicit operator StaticModInt(uint v)=>new StaticModInt((long)v);[MethodImpl(256)]public static implicit operator StaticModInt(long v)=>new StaticModInt(v);[MethodImpl(256)]public static implicit operator StaticModInt(ulong v)=>new StaticModInt(v);[MethodImpl(256)]public static implicit operator long(StaticModIntv)=>v._v;[MethodImpl(256)]public static implicit operator ulong(StaticModIntv)=>v._v;[MethodImpl(256)]public StaticModIntPow(long n){var x=this;var r=new StaticModInt(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 StaticModIntInv()=>new StaticModInt(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 StaticModIntm&&Equals(m);[MethodImpl(256)]public bool Equals(StaticModIntother)=>_v==other._v;[MethodImpl(256)]public override int GetHashCode()=>_v.GetHashCode();}} public static class Montgomery{public static uint MOD{get;private set;}const int L=31;const ulong mask=(1UL<>=1;vi<<=1;}}}[MethodImpl(256)]public static ulong Reduction(ulong t){ulong c=t*nr;c&=mask;c*=MOD;c+=t;c>>=L;if(c>=MOD)c-=MOD;return c;}[MethodImpl(256)]public static ulong Transform(ulong t)=>Reduction(t*r2);[MethodImpl(256)]public static ulong Mul(ulong a,ulong b)=>Reduction(Reduction(a*b)*r2);[MethodImpl(256)]public static uint Mul(uint a,uint b)=>(uint)Mul((ulong)a,b);[MethodImpl(256)]public static long Mul(long a,long b)=>(long)Mul((ulong)a,(ulong)b);[MethodImpl(256)]public static int Mul(int a,int b)=>(int)Mul((ulong)a,(ulong)b);[MethodImpl(256)]public static ulong Pow(ulong a,ulong b){ulong p=Transform(a),x=Transform(1);while(b>0){if((b&1)==1)x=Reduction(x*p);p=Reduction(p*p);b>>=1;}return Reduction(x);}} namespace Lib{public static class OutputLib{[MethodImpl(256)]public static void WriteJoin(string s,IEnumerablet)=>Console.WriteLine(string.Join(s,t));[MethodImpl(256)]public static void WriteMat(T[,]a,string sep=" "){int sz1=a.GetLength(0),sz2=a.GetLength(1);var b=new T[sz2];for(int i=0;i(T[][]a,string sep=" "){for(int i=0;i(T[][]a,Funcmap,string sep=" "){for(int i=0;imap(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