結果
| 問題 | No.2877 Gunegune Hyperion |
| ユーザー |
 KumaTachiRen
|
| 提出日時 | 2024-09-06 23:44:47 |
| 言語 | C# (.NET 8.0.203) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 22,036 bytes |
| コンパイル時間 | 8,583 ms |
| コンパイル使用メモリ | 166,948 KB |
| 実行使用メモリ | 69,244 KB |
| 最終ジャッジ日時 | 2024-09-06 23:45:04 |
| 合計ジャッジ時間 | 16,727 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 50 ms
27,648 KB |
| testcase_01 | AC | 48 ms
24,064 KB |
| testcase_02 | AC | 120 ms
29,440 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| 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 を復元しました (94 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(164,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/
ソースコード
using Lib;
using Lib.MathLib;
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.Text;
using static Lib.Functions;
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 };
var x = new ModInt[25][];
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
{
if (Math.Abs(i - j) <= 1)
{
x[5 * i + j] = new ModInt[b[j] + 1];
x[5 * i + j][b[j]] = a[i, j];
}
else
{
x[5 * i + j] = new ModInt[0];
}
}
var inv5 = ((ModInt)5).Inv();
var y = new ModInt[5][];
for (int i = 0; i < 5; i++)
{
y[i] = new ModInt[b[i] + 1];
y[i][b[i]] = inv5;
}
uint mod = 998244353;
ACLButterfly.Init(mod);
StaticModInt<Mod>[] Conv<Mod>(ReadOnlySpan<StaticModInt<Mod>> a, ReadOnlySpan<StaticModInt<Mod>> b) where Mod : struct, IStaticMod
{
if (a.Length == 0 || b.Length == 0) return new StaticModInt<Mod>[0];
int l = a.Length + b.Length - 1;
int n = 1;
while (n < l) n <<= 1;
var f = new uint[n];
var g = new uint[n];
for (int i = 0; i < a.Length; i++) f[i] = (uint)a[i].Value;
for (int i = 0; i < b.Length; i++) g[i] = (uint)b[i].Value;
ACLButterfly.Calc(f);
ACLButterfly.Calc(g);
for (int i = 0; i < f.Length; i++) f[i] = (uint)((ulong)f[i] * g[i] % mod);
ACLButterfly.CalcInv(f);
var r = new StaticModInt<Mod>[a.Length + b.Length - 1];
var inv = new StaticModInt<Mod>(n).Inv();
for (int i = 0; i < r.Length; i++) r[i] = f[i] * inv;
return r;
}
ModInt[][] Mul(ModInt[][] a, ModInt[][] b)
{
var c = new ModInt[25][];
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
{
int l = 0;
for (int k = 0; k < 5; k++) Chmax(ref l, a[5 * i + k].Length + b[5 * k + j].Length - 1);
var f = new ModInt[l];
for (int k = 0; k < 5; k++)
{
var g = Conv<Mod998244353>(a[5 * i + k], b[5 * k + j]);
for (int h = 0; h < g.Length; h++) f[h] += g[h];
}
c[5 * i + j] = f;
}
return c;
}
n--;
while (n > 0)
{
if (n % 2 == 1)
{
var z = new ModInt[5][];
for (int k = 0; k < 5; k++)
{
int l = 0;
for (int i = 0; i < 5; i++) Chmax(ref l, y[i].Length + x[5 * i + k].Length - 1);
var f = new ModInt[l];
for (int i = 0; i < 5; i++)
{
var g = Conv<Mod998244353>(y[i], x[5 * 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 < 5; 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<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 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<<x)<n)x++;return x;}[MethodImpl(256)]public static int SafeMod(int x,int m){int r=x%m;return r<0?r+Math.Abs(m):r;}[MethodImpl(256)]public static long SafeMod(long x,long m){long r=x%m;return r<0?r+Math.Abs(m):r;}[MethodImpl(256)]public static bool IsIncreasing(long a,long b,long c)=>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<T>(ref T x,ref T y){T t=y;y=x;x=t;}[MethodImpl(256)]public static T Clamp<T>(T x,T l,T r)where T:IComparable<T> =>x.CompareTo(l)<=0?l:(x.CompareTo(r)<=0?x:r);[MethodImpl(256)]public static T Clamp<T>(ref T x,T l,T r)where T:IComparable<T> =>x=x.CompareTo(l)<=0?l:(x.CompareTo(r)<=0?x:r);[MethodImpl(256)]public static void Chmin<T>(ref T x,T y)where T:IComparable<T>{if(x.CompareTo(y)>0)x=y;}[MethodImpl(256)]public static void Chmax<T>(ref T x,T y)where T:IComparable<T>{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>(T[]arr,T val,int l=-1,int r=-1)where T:IComparable<T> =>LowerBound(arr.AsSpan(),t=>t.CompareTo(val),l,r);[MethodImpl(256)]public static int LowerBound<T>(T[]arr,Func<T,int>comp,int l=-1,int r=-1)=>LowerBound(arr.AsSpan(),comp,l,r);[MethodImpl(256)]public static int LowerBound<T>(Span<T>data,Func<T,int>comp,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<r){int x=(l+r)/2;if(comp(data[x])<0)l=x+1;else r=x;}return l;}[MethodImpl(256)]public static int RangeCount<T>(T[]arr,T geq,T lt,int l=-1,int r=-1)where T:IComparable<T> =>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<digit;i++)c[digit-1-i]=((v>>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<digit;i++,v/=n)c[digit-1-i]=(int)(v%n);return string.Join("",c);}}}
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.MathLib{public static class ACLButterfly{public static uint Mod{get;private set;}static uint g;static int rank2;static ulong[]root,iroot;static ulong[]rate2,irate2;static ulong[]rate3,irate3;[MethodImpl(256)]static ulong Pow(ulong x,uint n){ulong y=1;for(;n>0;n>>=1){if((n&1)==1)y=y*x%Mod;x=x*x%Mod;}return y;}[MethodImpl(256)]static ulong Inv(ulong x)=>Pow(x,Mod-2);public static void Init(uint mod){Mod=mod;g=(uint)PrimitiveRoot.Calc((int)mod);rank2=BitOperations.TrailingZeroCount(Mod-1);root=new ulong[rank2+1];iroot=new ulong[rank2+1];rate2=new ulong[Math.Max(0,rank2-2+1)];irate2=new ulong[Math.Max(0,rank2-2+1)];rate3=new ulong[Math.Max(0,rank2-3+1)];irate3=new ulong[Math.Max(0,rank2-3+1)];root[rank2]=Pow(g,(Mod-1)>>rank2);iroot[rank2]=Inv(root[rank2]);for(int i=rank2-1;i>=0;i--){root[i]=root[i+1]*root[i+1]%Mod;iroot[i]=iroot[i+1]*iroot[i+1]%Mod;}{ulong prod=1,iprod=1;for(int i=0;i<=rank2-2;i++){rate2[i]=root[i+2]*prod%Mod;irate2[i]=iroot[i+2]*iprod%Mod;prod=prod*iroot[i+2]%Mod;iprod=iprod*root[i+2]%Mod;}}{ulong prod=1,iprod=1;for(int i=0;i<=rank2-3;i++){rate3[i]=root[i+3]*prod%Mod;irate3[i]=iroot[i+3]*iprod%Mod;prod=prod*iroot[i+3]%Mod;iprod=iprod*root[i+3]%Mod;}}}[MethodImpl(256)]public static void Calc(Span<uint>a){int n=a.Length;int h=BitOperations.TrailingZeroCount(n);int len=0;while(len<h){if(h-len==1){int p=1<<(h-len-1);ulong rot=1;for(int s=0;s<(1<<len);s++){int offset=s<<(h-len);for(int i=0;i<p;i++){uint l=a[i+offset];uint r=(uint)(a[i+offset+p]*rot%Mod);a[i+offset]=l+r;if(a[i+offset]>=Mod)a[i+offset]-=Mod;a[i+offset+p]=l-r;if(a[i+offset+p]>=Mod)a[i+offset+p]+=Mod;}if(s+1!=(1<<len))rot=rot*rate2[BitOperations.TrailingZeroCount(~s)]%Mod;}len++;}else{int p=1<<(h-len-2);ulong rot=1,imag=root[2];for(int s=0;s<(1<<len);s++){ulong rot2=rot*rot%Mod;ulong rot3=rot2*rot%Mod;int offset=s<<(h-len);for(int i=0;i<p;i++){ulong mod2=(ulong)Mod*Mod;ulong a0=a[i+offset];ulong a1=a[i+offset+p]*rot;ulong a2=a[i+offset+2*p]*rot2;ulong a3=a[i+offset+3*p]*rot3;ulong a1na3imag=(a1+mod2-a3)%Mod*imag;ulong na2=mod2-a2;a[i+offset]=(uint)((a0+a2+a1+a3)%Mod);a[i+offset+1*p]=(uint)((a0+a2+(2*mod2-(a1+a3)))%Mod);a[i+offset+2*p]=(uint)((a0+na2+a1na3imag)%Mod);a[i+offset+3*p]=(uint)((a0+na2+(mod2-a1na3imag))%Mod);}if(s+1!=(1<<len))rot=rot*rate3[BitOperations.TrailingZeroCount(~s)]%Mod;}len+=2;}}}[MethodImpl(256)]public static void CalcInv(Span<uint>a){int n=a.Length;int h=BitOperations.TrailingZeroCount(n);int len=h;while(len>0){if(len==1){int p=1<<(h-len);ulong irot=1;for(int s=0;s<(1<<(len-1));s++){int offset=s<<(h-len+1);for(int i=0;i<p;i++){uint l=a[i+offset];uint r=a[i+offset+p];a[i+offset]=l+r;if(a[i+offset]>=Mod)a[i+offset]-=Mod;a[i+offset+p]=(uint)((Mod+l-r)*irot%Mod);}if(s+1!=(1<<(len-1)))irot=irot*irate2[BitOperations.TrailingZeroCount(~s)]%Mod;}len--;}else{int p=1<<(h-len);ulong irot=1,iimag=iroot[2];for(int s=0;s<(1<<(len-2));s++){ulong irot2=irot*irot%Mod;ulong irot3=irot2*irot%Mod;int offset=s<<(h-len+2);for(int i=0;i<p;i++){ulong a0=a[i+offset+0*p];ulong a1=a[i+offset+1*p];ulong a2=a[i+offset+2*p];ulong a3=a[i+offset+3*p];ulong a2na3iimag=(Mod+a2-a3)*iimag%Mod;a[i+offset]=(uint)((a0+a1+a2+a3)%Mod);a[i+offset+1*p]=(uint)((a0+(Mod-a1)+a2na3iimag)*irot%Mod);a[i+offset+2*p]=(uint)((a0+a1+(Mod-a2)+(Mod-a3))*irot2%Mod);a[i+offset+3*p]=(uint)((a0+(Mod-a1)+(Mod-a2na3iimag))*irot3%Mod);}if(s+1!=(1<<(len-2)))irot=irot*irate3[BitOperations.TrailingZeroCount(~s)]%Mod;}len-=2;}}}}}
namespace Lib.MathLib{public static class PrimitiveRoot{public static int Calc(int p){if(p==2)return 1;if(p==3)return 2;if(p==5)return 2;int q=p-1;var pf=new List<int>();for(int x=2;(long)x*x<=q;x+=(x&1)+1){if(q%x!=0)continue;pf.Add(x);while(q%x==0)q/=x;}if(q>1)pf.Add(q);q=p-1;var rnd=new XORShift.XORShift32();while(true){int r=(int)(rnd.Next()%(p-2))+2;bool ok=true;for(int i=0;ok&&i<pf.Count;i++){int n=q/pf[i];long x=r,y=1;while(n>0){if(n%2==1)y=y*x%p;x=x*x%p;n/=2;}if(y==1)ok=false;}if(ok)return r;}}}}
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();}}
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 Lib{public class XORShift{public class XORShift32{uint x;public XORShift32(){x=2463534242;}public uint Next(){x^=x<<13;x^=x>>17;x^=x<<5;return x;}}public class XORShift64{ulong x;public XORShift64(){x=88172645463325252;}public ulong Next(){x^=x<<13;x^=x>>7;x^=x<<17;return x;}}}}
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