結果

問題 No.2877 Gunegune Hyperion
ユーザー KumaTachiRenKumaTachiRen
提出日時 2024-09-06 23:32:53
言語 C#
(.NET 8.0.203)
結果
TLE  
実行時間 -
コード長 23,845 bytes
コンパイル時間 9,462 ms
コンパイル使用メモリ 169,256 KB
実行使用メモリ 219,660 KB
最終ジャッジ日時 2024-09-06 23:34:15
合計ジャッジ時間 42,922 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
28,288 KB
testcase_01 AC 53 ms
25,216 KB
testcase_02 AC 84 ms
27,904 KB
testcase_03 AC 1,808 ms
75,048 KB
testcase_04 AC 1,964 ms
74,788 KB
testcase_05 AC 4,049 ms
117,180 KB
testcase_06 AC 4,054 ms
124,452 KB
testcase_07 AC 4,386 ms
219,660 KB
testcase_08 AC 4,374 ms
129,856 KB
testcase_09 AC 4,284 ms
168,348 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (95 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
/home/judge/data/code/Main.cs(124,3674): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using Lib;
using ModInt = Lib.StaticModInt<Lib.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.Text;
using static Lib.OutputLib;
public class Solver
{
    const bool MultiTestCase = false;
    void Solve()
    {
        int n = ri, h = ri;

        var a = new ModInt[5, 5];
        for (int i = 0; i < 5; i++)
        {
            int c = 0;
            for (int j = 0; j < 5; j++) if (Math.Abs(i - j) <= 1) c++;
            var inv = ((ModInt)c).Inv();
            for (int j = 0; j < 5; j++) if (Math.Abs(i - j) <= 1) a[i, j] = inv;
        }
        var b = new int[5] { 0, 1, 1, 1, 0 };

        int m = 2;
        while (m < n) m <<= 1;

        var x = new ModInt[5 * 5 * m];
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
            {
                if (Math.Abs(i - j) <= 1)
                {
                    var f = new ModInt[m];
                    f[b[j]] = a[i, j];
                    Butterfly<Mod998244353>.Calculate(f);
                    for (int k = 0; k < m; k++) x[k * 25 + 5 * i + j] = f[k];
                }
            }
        var y = new ModInt[5 * 5 * m];
        for (int i = 0; i < 5; i++)
            for (int k = 0; k < m; k++) y[k * 25 + 5 * i + i] = 1;

        ModInt[] Mul(ReadOnlySpan<ModInt> a, ReadOnlySpan<ModInt> b)
        {
            var c = new ModInt[5 * 5 * m];
            for (int i = 0; i < 5; i++)
                for (int j = 0; j < 5; j++)
                    for (int l = 0; l < m; l++)
                    {
                        ModInt v = 0;
                        for (int k = 0; k < 5; k++)
                            v += a[25 * l + 5 * i + k] * b[25 * l + 5 * k + j];
                        c[25 * l + 5 * i + j] = v;
                    }
            return c;
        }

        n--;
        while (n > 0)
        {
            if (n % 2 == 1) y = Mul(y, x);
            x = Mul(x, x);
            n /= 2;
        }


        ModInt ans = 0;
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
            {
                var f = new ModInt[m];
                for (int k = 0; k < m; k++) f[k] = y[25 * k + 5 * i + j];
                Butterfly<Mod998244353>.CalculateInv(f);
                int v = b[i];
                for (int u = 0; u < f.Length; u++) if (u + v >= h) ans += f[u];
            }
        ans /= 5 * m;
        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<T>(out T[] a, int n, Func<T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(); }
    void ReadArray<T>(out T[] a, int n, Func<int, T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(i); }
}

static class Program
{
    static public void Main(string[] args)
    {
        SourceExpander.Expander.Expand();
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        new Solver();
        Console.Out.Flush();
    }
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace Lib{public static class InternalBit{[MethodImpl(256)]public static uint ExtractLowestSetBit(int n){if(System.Runtime.Intrinsics.X86.Bmi1.IsSupported)return System.Runtime.Intrinsics.X86.Bmi1.ExtractLowestSetBit((uint)n);return(uint)(n&-n);}[MethodImpl(256)]public static int Bsf(uint n){return BitOperations.TrailingZeroCount(n);}[MethodImpl(256)]public static int CeilPow2(int n){var un=(uint)n;if(un<=1)return 0;return BitOperations.Log2(un-1)+1;}}}
namespace Lib{public partial class StreamScanner{public int[][]ReadUnweightedTree(int n,int origin=1){var gr=new List<int>[n];for(int i=0;i<n;i++)gr[i]=new List<int>();for(int i=0;i<n-1;i++){int u=(int)(Integer()-origin);int v=(int)(Integer()-origin);gr[u].Add(v);gr[v].Add(u);}var g=new int[n][];for(int i=0;i<n;i++)g[i]=gr[i].ToArray();return g;}}}
namespace Lib{public partial class StreamScanner{public StreamScanner(Stream stream){str=stream;}private readonly Stream str;private readonly byte[]buf=new byte[1024];private int len,ptr;public bool isEof=false;public bool IsEndOfStream{get{return isEof;}}[MethodImpl(256)]private byte Read(){if(isEof)throw new EndOfStreamException();if(ptr>=len){ptr=0;if((len=str.Read(buf,0,1024))<=0){isEof=true;return 0;}}return buf[ptr++];}[MethodImpl(256)]public char Char(){byte b=0;do b=Read();while(b<33||126<b);return(char)b;}[MethodImpl(256)]public string Line(){var sb=new StringBuilder();for(var b=Char();b!=10&&!isEof;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public string Scan(){var sb=new StringBuilder();for(var b=Char();b>=33&&b<=126;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public long Integer(){long ret=0;byte b=0;var ng=false;do b=Read();while(b!='-'&&(b<'0'||'9'<b));if(b=='-'){ng=true;b=Read();}for(;true;b=Read()){if(b<'0'||'9'<b)return ng?-ret:ret;else ret=ret*10+b-'0';}}[MethodImpl(256)]public ulong UInteger(){ulong ret=0;byte b=0;do b=Read();while(b<'0'||'9'<b);for(;true;b=Read()){if(b<'0'||'9'<b)return ret;else ret=ret*10+b-'0';}}[MethodImpl(256)]public double Double()=>double.Parse(Scan());}}
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(Span<uint>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector<uint>.Count;var modV=new Vector<uint>(Mod);for(int ph=1;ph<=h;ph++){int w=1<<(ph-1);int p=1<<(h-ph);uint now=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=Montgomery.Mul(rs[i],now);ls[i]=l+r;if(ls[i]>=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<ls.Length;i+=regLength){var lsSliced=ls.Slice(i);var rsSliced=rs.Slice(i);var u=new Vector<uint>(lsSliced);var v=new Vector<uint>(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(Span<uint>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector<uint>.Count;var modV=new Vector<uint>(Mod);for(int ph=h;ph>=1;ph--){int w=1<<(ph-1);int p=1<<(h-ph);uint iNow=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;if(ls[i]>=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<ls.Length;i+=regLength){var lsSliced=ls.Slice(i);var rsSliced=rs.Slice(i);var u=new Vector<uint>(lsSliced);var v=new Vector<uint>(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];Span<uint>es=stackalloc uint[cnt2-1];Span<uint>ies=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];Span<uint>es=stackalloc uint[cnt2-1];Span<uint>ies=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 Butterfly<T>where T:struct,IStaticMod{public static readonly StaticModInt<T>[]sumE=CalcurateSumE();public static readonly StaticModInt<T>[]sumIE=CalcurateSumIE();public static readonly uint Mod=default(T).Mod;[MethodImpl(256)]public static void Calculate(Span<StaticModInt<T>>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector<uint>.Count;var modV=new Vector<uint>(Mod);for(int ph=1;ph<=h;ph++){int w=1<<(ph-1);int p=1<<(h-ph);var now=StaticModInt<T>.Raw(1);for(int s=0;s<w;s++){int offset=s<<(h-ph+1);var ls=a.Slice(offset,p);var rs=a.Slice(offset+p,p);if(p<regLength){for(int i=0;i<p;i++){var l=ls[i];var r=rs[i]*now;ls[i]=l+r;rs[i]=l-r;}}else{foreach(ref var r in rs){r*=now;}var lu=MemoryMarshal.Cast<StaticModInt<T>,uint>(ls);var ru=MemoryMarshal.Cast<StaticModInt<T>,uint>(rs);for(int i=0;i<lu.Length;i+=regLength){var luSliced=lu.Slice(i);var ruSliced=ru.Slice(i);var u=new Vector<uint>(luSliced);var v=new Vector<uint>(ruSliced);var add=u+v;var sub=u-v;var ge=Vector.GreaterThanOrEqual(add,modV);add=Vector.ConditionalSelect(ge,add-modV,add);ge=Vector.GreaterThanOrEqual(sub,modV);sub=Vector.ConditionalSelect(ge,sub+modV,sub);add.CopyTo(luSliced);sub.CopyTo(ruSliced);}}now*=sumE[InternalBit.Bsf(~(uint)s)];}}}[MethodImpl(256)]public static void CalculateInv(Span<StaticModInt<T>>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector<uint>.Count;var modV=new Vector<uint>(Mod);for(int ph=h;ph>=1;ph--){int w=1<<(ph-1);int p=1<<(h-ph);var iNow=StaticModInt<T>.Raw(1);for(int s=0;s<w;s++){int offset=s<<(h-ph+1);var ls=a.Slice(offset,p);var rs=a.Slice(offset+p,p);if(p<regLength){for(int i=0;i<p;i++){var l=ls[i];var r=rs[i];ls[i]=l+r;rs[i]=StaticModInt<T>.Raw((int)((ulong)(Mod+l.Value-r.Value)*(ulong)iNow.Value%Mod));}}else{var lu=MemoryMarshal.Cast<StaticModInt<T>,uint>(ls);var ru=MemoryMarshal.Cast<StaticModInt<T>,uint>(rs);for(int i=0;i<lu.Length;i+=regLength){var luSliced=lu.Slice(i);var ruSliced=ru.Slice(i);var u=new Vector<uint>(luSliced);var v=new Vector<uint>(ruSliced);var add=u+v;var sub=u-v;var ge=Vector.GreaterThanOrEqual(add,modV);add=Vector.ConditionalSelect(ge,add-modV,add);sub+=modV;add.CopyTo(luSliced);sub.CopyTo(ruSliced);}foreach(ref var r in rs){r*=iNow;}}iNow*=sumIE[InternalBit.Bsf(~(uint)s)];}}}public static StaticModInt<T>[]CalcurateSumE(){int g=InternalMath.PrimitiveRoot<T>();int cnt2=InternalBit.Bsf(default(T).Mod-1);var e=new StaticModInt<T>(g).Pow((default(T).Mod-1)>>cnt2);var ie=e.Inv();var sumE=new StaticModInt<T>[30];Span<StaticModInt<T>>es=stackalloc StaticModInt<T>[cnt2-1];Span<StaticModInt<T>>ies=stackalloc StaticModInt<T>[cnt2-1];for(int i=es.Length-1;i>=0;i--){es[i]=e;ies[i]=ie;e*=e;ie*=ie;}var now=StaticModInt<T>.Raw(1);for(int i=0;i<=cnt2-2;i++){sumE[i]=es[i]*now;now*=ies[i];}return sumE;}public static StaticModInt<T>[]CalcurateSumIE(){int g=InternalMath.PrimitiveRoot<T>();int cnt2=InternalBit.Bsf(default(T).Mod-1);var e=new StaticModInt<T>(g).Pow((default(T).Mod-1)>>cnt2);var ie=e.Inv();var sumIE=new StaticModInt<T>[30];Span<StaticModInt<T>>es=stackalloc StaticModInt<T>[cnt2-1];Span<StaticModInt<T>>ies=stackalloc StaticModInt<T>[cnt2-1];for(int i=es.Length-1;i>=0;i--){es[i]=e;ies[i]=ie;e*=e;ie*=ie;}var now=StaticModInt<T>.Raw(1);for(int i=0;i<=cnt2-2;i++){sumIE[i]=ies[i]*now;now*=es[i];}return sumIE;}[Conditional("ATCODER_CONTRACT")]private static void CheckPow2(int n){if(BitOperations.PopCount((uint)n)!=1){throw new ArgumentException("配列長は2のべき乗でなければなりません。");}}}}
namespace Lib{public static class InternalMath{private static readonly Dictionary<uint,int>primitiveRootsCache=new Dictionary<uint,int>(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};[MethodImpl(256)]public static int PrimitiveRoot<TMod>()where TMod:struct,IStaticMod{uint m=default(TMod).Mod;if(primitiveRootsCache.TryGetValue(m,out var p))return p;return primitiveRootsCache[m]=PrimitiveRootCalculate<TMod>();}static int PrimitiveRootCalculate<TMod>()where TMod:struct,IStaticMod{var m=default(TMod).Mod;Span<uint>divs=stackalloc uint[20];divs[0]=2;int cnt=1;var x=m-1;x>>=BitOperations.TrailingZeroCount(x);for(uint i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;do{x/=i;}while(x%i==0);}}if(x>1){divs[cnt++]=x;}divs=divs.Slice(0,cnt);for(int g=2;;g++){foreach(var d in divs)if(new StaticModInt<TMod>(g).Pow((m-1)/d).Value==1)goto NEXT;return g;NEXT:;}}[MethodImpl(256)]public static int PrimitiveRoot(uint m){if(primitiveRootsCache.TryGetValue(m,out var p))return p;return primitiveRootsCache[m]=PrimitiveRootCalculate(m);}static int PrimitiveRootCalculate(uint m){Span<uint>divs=stackalloc uint[20];divs[0]=2;int cnt=1;var x=m-1;x>>=BitOperations.TrailingZeroCount(x);for(uint i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;do{x/=i;}while(x%i==0);}}if(x>1){divs[cnt++]=x;}divs=divs.Slice(0,cnt);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;ReadOnlySpan<byte>bases=stackalloc byte[3]{2,7,61};foreach(long a in bases){long t=d;long y=PowMod(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0){return false;}}return true;}[MethodImpl(256)]public static uint PowMod(long x,long n,int m){if(m==1)return 0;return new Barrett((uint)m).Pow(x,n);}[MethodImpl(256)]public static uint PowMod(long x,long n,uint m){if(m==1)return 0;return new Barrett(m).Pow(x,n);}[MethodImpl(256)]public static ulong FloorSumUnsigned(ulong n,ulong m,ulong a,ulong b){ulong ans=0;while(true){if(a>=m){ans+=(n-1)*n/2*(a/m);a%=m;}if(b>=m){ans+=n*(b/m);b%=m;}ulong yMax=a*n+b;if(yMax<m)return ans;(n,m,a,b)=(yMax/m,a,m,yMax%m);}}[MethodImpl(256)]public static ulong Mul128Bit(ulong a,ulong b){if(System.Runtime.Intrinsics.X86.Bmi2.X64.IsSupported)return System.Runtime.Intrinsics.X86.Bmi2.X64.MultiplyNoFlags(a,b);return Mul128BitLogic(a,b);}[MethodImpl(256)]internal static ulong Mul128BitLogic(ulong a,ulong b){var au=a>>32;var ad=a&0xFFFFFFFF;var bu=b>>32;var bd=b&0xFFFFFFFF;var l=ad*bd;var m1=au*bd;var m2=ad*bu;var h=au*bu;var lu=l>>32;var m1d=m1&0xFFFFFFFF;var m2d=m2&0xFFFFFFFF;var c=m1d+m2d+lu;return h+(m1>>32)+(m2>>32)+(c>>32);}}}
namespace Lib{public interface IStaticMod{uint Mod{get;}bool IsPrime{get;}}public readonly struct Mod1000000007:IStaticMod{public uint Mod=>1000000007;public bool IsPrime=>true;}public readonly struct Mod998244353:IStaticMod{public uint Mod=>998244353;public bool IsPrime=>true;}public readonly struct StaticModInt<T>:IEquatable<StaticModInt<T>>where T:struct,IStaticMod{internal readonly uint _v;private static readonly T op=default;public int Value=>(int)_v;public static int Mod=>(int)op.Mod;public static StaticModInt<T>Zero=>default;public static StaticModInt<T>One=>new StaticModInt<T>(1u);[MethodImpl(256)]public static StaticModInt<T>Raw(int v){var u=unchecked((uint)v);return new StaticModInt<T>(u);}[MethodImpl(256)]public StaticModInt(long v):this(Round(v)){}[MethodImpl(256)]public StaticModInt(ulong v):this((uint)(v%op.Mod)){}[MethodImpl(256)]private StaticModInt(uint v)=>_v=v;[MethodImpl(256)]private static uint Round(long v){var x=v%op.Mod;if(x<0)x+=op.Mod;return(uint)x;}[MethodImpl(256)]public static StaticModInt<T>operator ++(StaticModInt<T>v){var x=v._v+1;if(x==op.Mod)x=0;return new StaticModInt<T>(x);}[MethodImpl(256)]public static StaticModInt<T>operator --(StaticModInt<T>v){var x=v._v;if(x==0)x=op.Mod;return new StaticModInt<T>(x-1);}[MethodImpl(256)]public static StaticModInt<T>operator+(StaticModInt<T>lhs,StaticModInt<T>rhs){var v=lhs._v+rhs._v;if(v>=op.Mod)v-=op.Mod;return new StaticModInt<T>(v);}[MethodImpl(256)]public static StaticModInt<T>operator-(StaticModInt<T>lhs,StaticModInt<T>rhs){unchecked{var v=lhs._v-rhs._v;if(v>=op.Mod)v+=op.Mod;return new StaticModInt<T>(v);}}[MethodImpl(256)]public static StaticModInt<T>operator*(StaticModInt<T>lhs,StaticModInt<T>rhs)=>new StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));[MethodImpl(256)]public static StaticModInt<T>operator/(StaticModInt<T>lhs,StaticModInt<T>rhs)=>new StaticModInt<T>((uint)((ulong)lhs._v*Inv(rhs._v)%op.Mod));[MethodImpl(256)]public static StaticModInt<T>operator+(StaticModInt<T>v)=>v;[MethodImpl(256)]public static StaticModInt<T>operator-(StaticModInt<T>v)=>new StaticModInt<T>(v._v==0?0:op.Mod-v._v);[MethodImpl(256)]public static bool operator==(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v==rhs._v;[MethodImpl(256)]public static bool operator!=(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v!=rhs._v;[MethodImpl(256)]public static implicit operator StaticModInt<T>(int v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(uint v)=>new StaticModInt<T>((long)v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(long v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(ulong v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator long(StaticModInt<T>v)=>v._v;[MethodImpl(256)]public static implicit operator ulong(StaticModInt<T>v)=>v._v;[MethodImpl(256)]public StaticModInt<T>Pow(long n){var x=this;var r=new StaticModInt<T>(1U);if(n<0)(x,n)=(x.Inv(),-n);while(n>0){if((n&1)>0)r*=x;x*=x;n>>=1;}return r;}[MethodImpl(256)]public StaticModInt<T>Inv()=>new StaticModInt<T>(Inv(_v));[MethodImpl(256)]static ulong Inv(ulong x){long u=op.Mod,xu=1,yu=0,v=(long)x,xv=0,yv=1;while(v!=0){long w=SafeMod(u,v);long q=(u-w)/v;long xw=xu-xv*q;long yw=yu-yv*q;u=v;xu=xv;yu=yv;v=w;xv=xw;yv=yw;}return(ulong)(yu<0?yu+op.Mod:yu);}[MethodImpl(256)]static long SafeMod(long x,long m){long r=x%m;if(r<0)r+=m;return r;}[MethodImpl(256)]public override string ToString()=>_v.ToString();[MethodImpl(256)]public string ToString(string format,IFormatProvider formatProvider)=>_v.ToString(format,formatProvider);[MethodImpl(256)]public override bool Equals(object?obj)=>obj is StaticModInt<T>m&&Equals(m);[MethodImpl(256)]public bool Equals(StaticModInt<T>other)=>_v==other._v;[MethodImpl(256)]public override int GetHashCode()=>_v.GetHashCode();}}
public static class Montgomery{public static uint MOD{get;private set;}const int L=31;const ulong mask=(1UL<<L)-1;static ulong r2,nr;public static void Init(uint mod){if(MOD!=mod){MOD=mod;r2=(1UL<<(L<<1))%MOD;nr=0;ulong t=0,vi=1;for(int i=0;i<L;i++){if((t&1)==0){t+=MOD;nr+=vi;}t>>=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<T>(string s,IEnumerable<T>t)=>Console.WriteLine(string.Join(s,t));[MethodImpl(256)]public static void WriteMat<T>(T[,]a,string sep=" "){int sz1=a.GetLength(0),sz2=a.GetLength(1);var b=new T[sz2];for(int i=0;i<sz1;i++){for(int j=0;j<sz2;j++)b[j]=a[i,j];WriteJoin(sep,b);}}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,string sep=" "){for(int i=0;i<a.Length;i++)WriteJoin(sep,a[i]);}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,Func<T,string>map,string sep=" "){for(int i=0;i<a.Length;i++)WriteJoin(sep,a[i].Select(x=>map(x)));}[MethodImpl(256)]public static void Write(object t)=>Console.WriteLine(t.ToString());[MethodImpl(256)]public static void Write(params object[]arg)=>Console.WriteLine(string.Join(" ",arg.Select(x=>x.ToString())));[MethodImpl(256)]public static void Write(string str)=>Console.WriteLine(str);[MethodImpl(256)]public static void WriteFlush(object t){Console.WriteLine(t.ToString());Console.Out.Flush();}[MethodImpl(256)]public static void WriteError(object t)=>Console.Error.WriteLine(t.ToString());[MethodImpl(256)]public static void Flush()=>Console.Out.Flush();[MethodImpl(256)]public static void YN(bool t)=>Console.WriteLine(t?"YES":"NO");[MethodImpl(256)]public static void Yn(bool t)=>Console.WriteLine(t?"Yes":"No");[MethodImpl(256)]public static void yn(bool t)=>Console.WriteLine(t?"yes":"no");[MethodImpl(256)]public static void DeleteLine()=>Console.Write("\x1b[1A\x1b[2K");[MethodImpl(256)]public static void ProgressBar(long now,long total,int blocks=50){int x=(int)((2*now*blocks+1)/(2*total));Console.Write($"\x1b[G[\x1b[42m{string.Concat(Enumerable.Repeat("_",x))}\x1b[0m{string.Concat(Enumerable.Repeat("_",blocks-x))}] : {now} / {total}");}}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander
0