提出 #29591012

---

ソースコード 拡げる

using AtCoder.Internal;
using AtCoder.Operators;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using ModInt = AtCoder.StaticModInt<AtCoder.Mod998244353>;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics.X86;
using System.Text;
partial class Program
{
    string YesNo(bool b) => b ? "Yes" : "No";
    const bool __ManyTestCases = false;
    [MethodImpl(MethodImplOptions.AggressiveOptimization)]
    private object Calc()
    {
        N = cr;
        A = cr.Repeat(N);
        B = cr.Repeat(N);
        Array.Sort(A, B);
        var dp = new ModInt[N][];
        dp[0] = new ModInt[5001].Fill(1);
        if (B[0] < dp[0].Length)
            dp[0].AsSpan(B[0]).Fill(2);
        for (int i = 1; i < dp.Length; i++)
        {
            dp[i] = new ModInt[5001];
            var bb = B[i];
            for (int p = dp[i].Length - 1; p >= 0; p--)
            {
                dp[i][p] = dp[i - 1][p] + dp.GetOrDummy(i - 1, p - bb);
            }
        }
        ModInt s = A[0] >= B[0] ? 1 : 0;
        for (int i = 1; i < dp.Length; i++)
        {
            var d = A[i] - B[i];
            if (d < 0) continue;
            s += dp[i - 1][d];
        }
        return s;
    }
    int N;
    int[] A;
    int[] B;
}
#region Expanded by https://github.com/kzrnm/SourceExpander
//LICENSE:
//https://github.com/kzrnm/Kzrnm.Competitive/blob/master/LICENSE
//https://github.com/kzrnm/Kzrnm.Competitive/blob/master/3rd-party%20Licenses.txt
#pragma warning disable
namespace AtCoder.Internal{using static MethodImplOptions;public static class InternalBit{[MethodImpl(AggressiveInlining)]public static uint ExtractLowestSetBit(int n){if(Bmi1.IsSupported){return Bmi1.ExtractLowestSetBit((uint)n);}return(uint)(n&-n);}[MethodImpl(AggressiveInlining)]public static int BSF(uint n){return BitOperations.TrailingZeroCount(n);}[MethodImpl(AggressiveInlining)]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 class Barrett{public readonly uint Mod;internal readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public uint Mul(uint a,uint b){var z=(ulong)a*b;if(Bmi2.X64.IsSupported){var x=Bmi2.X64.MultiplyNoFlags(z,IM);var v=unchecked((uint)(z-x*Mod));if(Mod<=v)v+=Mod;return v;}return(uint)(z%Mod);}}}
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();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.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)];}}}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.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)];}}}private 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;}private 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 AtCoder.Internal{public static partial class InternalMath{private static readonly Dictionary<uint,int>primitiveRootsCache=new Dictionary<uint,int>(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};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{int m=(int)default(TMod).Mod;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;}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:{}}}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(MethodImplOptions.AggressiveInlining)]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;}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);}}}}
namespace AtCoder{public static partial class MathLib{public static StaticModInt<TMod>[]Convolution<TMod>(StaticModInt<TMod>[]a,StaticModInt<TMod>[]b)where TMod:struct,IStaticMod=>Convolution((ReadOnlySpan<StaticModInt<TMod>>)a,b);public static 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);return ConvolutionFFT(a,b);}private static StaticModInt<TMod>[]ConvolutionFFT<TMod>(ReadOnlySpan<StaticModInt<TMod>>a,ReadOnlySpan<StaticModInt<TMod>>b)where TMod:struct,IStaticMod{int n=a.Length,m=b.Length;int z=1<<InternalBit.CeilPow2(n+m-1);var a2=new StaticModInt<TMod>[z];var b2=new StaticModInt<TMod>[z];a.CopyTo(a2);b.CopyTo(b2);var result=ConvolutionFFTInner(a2,b2);Array.Resize(ref result,n+m-1);var iz=new StaticModInt<TMod>(z).Inv();for(int i=0;i<result.Length;i++)result[i]*=iz;return result;}private static StaticModInt<TMod>[]ConvolutionFFTInner<TMod>(StaticModInt<TMod>[]a,StaticModInt<TMod>[]b)where TMod:struct,IStaticMod{Butterfly<TMod>.Calculate(a);Butterfly<TMod>.Calculate(b);for(int i=0;i<a.Length;i++)a[i]*=b[i];Butterfly<TMod>.CalculateInv(a);return a;}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;}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;const ulong i1=190329765;const ulong i2=58587104;const ulong i3=187290749;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];for(int i=0;i<c.Length;i++){ulong x=0;x+=((ulong)c1[i]*i1)%Mod1*M2M3;x+=((ulong)c2[i]*i2)%Mod2*M1M3;x+=((ulong)c3[i]*i3)%Mod3*M1M2;long diff=c1[i]-InternalMath.SafeMod((long)x,(long)Mod1);if(diff<0){diff+=(long)Mod1;}switch(diff%5){case 2:x-=M1M2M3;break;case 3:x-=2*M1M2M3;break;case 4:x-=3*M1M2M3;break;}c[i]=(long)x;}return c;}}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;}}}
namespace AtCoder{public static partial class MathLib{public static Int32[]Convolution(Int32[]a,Int32[]b)=>Convolution<Mod998244353>(a,b);public static Int32[]Convolution<TMod>(Int32[]a,Int32[]b)where TMod:struct,IStaticMod=>Convolution<TMod>(a.AsSpan(),b.AsSpan());public static Int32[]Convolution<TMod>(ReadOnlySpan<Int32>a,ReadOnlySpan<Int32>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<Int32>();}var a2=new StaticModInt<TMod>[n];var b2=new StaticModInt<TMod>[m];for(int i=0;i<a2.Length;i++){a2[i]=new StaticModInt<TMod>(a[i]);}for(int i=0;i<b2.Length;i++){b2[i]=new StaticModInt<TMod>(b[i]);}var c2=Convolution(a2,b2);var c=new Int32[n+m-1];for(int i=0;i<c.Length;i++){c[i]=(Int32)c2[i].Value;}return c;}public static UInt32[]Convolution(UInt32[]a,UInt32[]b)=>Convolution<Mod998244353>(a,b);public static UInt32[]Convolution<TMod>(UInt32[]a,UInt32[]b)where TMod:struct,IStaticMod=>Convolution<TMod>(a.AsSpan(),b.AsSpan());public static UInt32[]Convolution<TMod>(ReadOnlySpan<UInt32>a,ReadOnlySpan<UInt32>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<UInt32>();}var a2=new StaticModInt<TMod>[n];var b2=new StaticModInt<TMod>[m];for(int i=0;i<a2.Length;i++){a2[i]=new StaticModInt<TMod>(a[i]);}for(int i=0;i<b2.Length;i++){b2[i]=new StaticModInt<TMod>(b[i]);}var c2=Convolution(a2,b2);var c=new UInt32[n+m-1];for(int i=0;i<c.Length;i++){c[i]=(UInt32)c2[i].Value;}return c;}public static Int64[]Convolution(Int64[]a,Int64[]b)=>Convolution<Mod998244353>(a,b);public static Int64[]Convolution<TMod>(Int64[]a,Int64[]b)where TMod:struct,IStaticMod=>Convolution<TMod>(a.AsSpan(),b.AsSpan());public static Int64[]Convolution<TMod>(ReadOnlySpan<Int64>a,ReadOnlySpan<Int64>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<Int64>();}var a2=new StaticModInt<TMod>[n];var b2=new StaticModInt<TMod>[m];for(int i=0;i<a2.Length;i++){a2[i]=new StaticModInt<TMod>(a[i]);}for(int i=0;i<b2.Length;i++){b2[i]=new StaticModInt<TMod>(b[i]);}var c2=Convolution(a2,b2);var c=new Int64[n+m-1];for(int i=0;i<c.Length;i++){c[i]=(Int64)c2[i].Value;}return c;}public static UInt64[]Convolution(UInt64[]a,UInt64[]b)=>Convolution<Mod998244353>(a,b);public static UInt64[]Convolution<TMod>(UInt64[]a,UInt64[]b)where TMod:struct,IStaticMod=>Convolution<TMod>(a.AsSpan(),b.AsSpan());public static UInt64[]Convolution<TMod>(ReadOnlySpan<UInt64>a,ReadOnlySpan<UInt64>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<UInt64>();}var a2=new StaticModInt<TMod>[n];var b2=new StaticModInt<TMod>[m];for(int i=0;i<a2.Length;i++){a2[i]=new StaticModInt<TMod>(a[i]);}for(int i=0;i<b2.Length;i++){b2[i]=new StaticModInt<TMod>(b[i]);}var c2=Convolution(a2,b2);var c=new UInt64[n+m-1];for(int i=0;i<c.Length;i++){c[i]=(UInt64)c2[i].Value;}return c;}}}
namespace AtCoder{public static partial class MathLib{public static(long y,long m)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);}}}
namespace AtCoder{public static partial class MathLib{public static long FloorSum(long n,long m,long a,long b){var nn=(ulong)n;var mm=(ulong)m;ulong aa,bb;ulong ans=0;if(a<0){var a2=(ulong)InternalMath.SafeMod(a,m);ans-=nn*(nn-1)/2*((a2-(ulong)a)/mm);aa=a2;}else aa=(ulong)a;if(b<0){var b2=(ulong)InternalMath.SafeMod(b,m);ans-=nn*((b2-(ulong)b)/mm);bb=b2;}else bb=(ulong)b;return(long)(ans+InternalMath.FloorSumUnsigned(nn,mm,aa,bb));}}}
namespace AtCoder{public static partial class MathLib{public static long InvMod(long x,long m){var(g,res)=InternalMath.InvGCD(x,m);return res;}}}
namespace AtCoder{public static partial class MathLib{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;}}}
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)]StaticModInt<T>IDivisionOperator<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);}[MethodImpl(AggressiveInlining)]public StaticModInt(long v):this(Round(v)){}[MethodImpl(AggressiveInlining)]public StaticModInt(ulong v):this((uint)(v%op.Mod)){}[MethodImpl(AggressiveInlining)]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)=>new StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));[MethodImpl(AggressiveInlining)]public static StaticModInt<T>operator/(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs*rhs.Inv();[MethodImpl(AggressiveInlining)]public static StaticModInt<T>operator+(StaticModInt<T>value)=>value;[MethodImpl(AggressiveInlining)]public static StaticModInt<T>operator-(StaticModInt<T>value)=>new StaticModInt<T>(op.Mod-value._v);[MethodImpl(AggressiveInlining)]public static bool operator==(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v==rhs._v;[MethodImpl(AggressiveInlining)]public static bool operator!=(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v!=rhs._v;[MethodImpl(AggressiveInlining)]public static implicit operator StaticModInt<T>(int value)=>new StaticModInt<T>(value);[MethodImpl(AggressiveInlining)]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)=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 AtCoder.Operators{public interface IAdditionOperator<T>{T Add(T x,T y);}public interface ISubtractOperator<T>{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>,ISubtractOperator<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 IMinMaxValue<T>{T MinValue{get;}T MaxValue{get;}}public interface INumOperator<T>:IArithmeticOperator<T>,ICompareOperator<T>,IMinMaxValue<T>{}public interface IShiftOperator<T>{T LeftShift(T x,int y);T RightShift(T x,int y);}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter:IDisposable{private const int DefaultBufferSize=1<<12;public StreamWriter StreamWriter{get;}public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){StreamWriter=new StreamWriter(output,encoding,bufferSize);}public void Flush()=>StreamWriter.Flush();public ConsoleWriter WriteLine(){StreamWriter.WriteLine();return this;}public ConsoleWriter WriteLine<T>(T obj){StreamWriter.WriteLine(obj.ToString());return this;}public ConsoleWriter WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);public ConsoleWriter WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);public ConsoleWriter WriteLineJoin<TTuple>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++)col[i]=tuple[i];return WriteLineJoin(col);}public ConsoleWriter WriteLineJoin(params object[]col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>(T1 v1,T2 v2){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v2.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v3.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.Write(v3.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v4.ToString());return this;}public ConsoleWriter WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);public ConsoleWriter WriteLineGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}protected ConsoleWriter WriteMany<T>(char sep,IEnumerable<T>col){var en=col.GetEnumerator();if(!en.MoveNext())goto End;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}End:StreamWriter.WriteLine();return this;}public void Dispose()=>Flush();}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter{public ConsoleWriter WriteLine(ReadOnlySpan<char>obj){StreamWriter.WriteLine(obj);return this;}public ConsoleWriter WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);protected ConsoleWriter WriteMany<T>(char sep,ReadOnlySpan<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}StreamWriter.WriteLine();return this;}}}
namespace Kzrnm.Competitive.IO{using static MethodImplOptions;public class PropertyConsoleReader{private const int BufSize=1<<12;private readonly Stream input;private readonly Encoding encoding;internal readonly byte[]buffer=new byte[BufSize];internal int pos=0;internal int len=0;public PropertyConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding){}public PropertyConsoleReader(Stream input,Encoding encoding){this.input=input;this.encoding=encoding;}[MethodImpl(AggressiveInlining)]protected internal byte Read(){if( ++pos>=len){if((len=input.Read(buffer,0,buffer.Length))<=0){buffer[0]=10;}pos=0;}return buffer[pos];}public int Int{[MethodImpl(AggressiveInlining)]get{int res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public int Int0{[MethodImpl(AggressiveInlining)]get=>Int-1;}public uint UInt{[MethodImpl(AggressiveInlining)]get=>(uint)ULong;}public uint UInt0{[MethodImpl(AggressiveInlining)]get=>UInt-1;}public long Long{[MethodImpl(AggressiveInlining)]get{long res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public long Long0{[MethodImpl(AggressiveInlining)]get=>Long-1;}public ulong ULong{[MethodImpl(AggressiveInlining)]get{ulong res=0;byte b;do b=Read();while(b<'0');do{res=res*10+(b^(ulong)'0');b=Read();}while('0'<=b);return res;}}public ulong ULong0{[MethodImpl(AggressiveInlining)]get=>ULong-1;}public string String{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();;byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(' '<b);return encoding.GetString(sb.ToArray());}}public string Ascii{[MethodImpl(AggressiveInlining)]get{var sb=new StringBuilder();byte b;do b=Read();while(b<=' ');do{sb.Append((char)b);b=Read();}while(' '<b);return sb.ToString();}}public string Line{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}}public char Char{[MethodImpl(AggressiveInlining)]get{byte b;do b=Read();while(b<=' ');return(char)b;}}public double Double{[MethodImpl(AggressiveInlining)]get{return double.Parse(Ascii);}}public decimal Decimal{[MethodImpl(AggressiveInlining)]get{return decimal.Parse(Ascii);}}[MethodImpl(AggressiveInlining)]public static implicit operator int(PropertyConsoleReader cr)=>cr.Int;[MethodImpl(AggressiveInlining)]public static implicit operator uint(PropertyConsoleReader cr)=>cr.UInt;[MethodImpl(AggressiveInlining)]public static implicit operator long(PropertyConsoleReader cr)=>cr.Long;[MethodImpl(AggressiveInlining)]public static implicit operator ulong(PropertyConsoleReader cr)=>cr.ULong;[MethodImpl(AggressiveInlining)]public static implicit operator double(PropertyConsoleReader cr)=>cr.Double;[MethodImpl(AggressiveInlining)]public static implicit operator decimal(PropertyConsoleReader cr)=>cr.Decimal;[MethodImpl(AggressiveInlining)]public static implicit operator string(PropertyConsoleReader cr)=>cr.Ascii;}}
namespace Kzrnm.Competitive.IO{public struct PropertyRepeatReader{internal readonly PropertyConsoleReader cr;internal readonly int count;internal PropertyRepeatReader(PropertyConsoleReader cr,int count){this.cr=cr;this.count=count;}public string[]Line{get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.Line;return arr;}}public string[]String{get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.String;return arr;}}public string[]Ascii{get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.Ascii;return arr;}}public int[]Int{get{var arr=new int[count];for(var i=0;i<count;i++)arr[i]=cr.Int;return arr;}}public int[]Int0{get{var arr=new int[count];for(var i=0;i<count;i++)arr[i]=cr.Int0;return arr;}}public uint[]UInt{get{var arr=new uint[count];for(var i=0;i<count;i++)arr[i]=cr.UInt;return arr;}}public uint[]UInt0{get{var arr=new uint[count];for(var i=0;i<count;i++)arr[i]=cr.UInt0;return arr;}}public long[]Long{get{var arr=new long[count];for(var i=0;i<count;i++)arr[i]=cr.Long;return arr;}}public long[]Long0{get{var arr=new long[count];for(var i=0;i<count;i++)arr[i]=cr.Long0;return arr;}}public ulong[]ULong{get{var arr=new ulong[count];for(var i=0;i<count;i++)arr[i]=cr.ULong;return arr;}}public ulong[]ULong0{get{var arr=new ulong[count];for(var i=0;i<count;i++)arr[i]=cr.ULong0;return arr;}}public double[]Double{get{var arr=new double[count];for(var i=0;i<count;i++)arr[i]=cr.Double;return arr;}}public decimal[]Decimal{get{var arr=new decimal[count];for(var i=0;i<count;i++)arr[i]=cr.Decimal;return arr;}}public static implicit operator string[](PropertyRepeatReader rr)=>rr.Ascii;public static implicit operator int[](PropertyRepeatReader rr)=>rr.Int;public static implicit operator uint[](PropertyRepeatReader rr)=>rr.UInt;public static implicit operator long[](PropertyRepeatReader rr)=>rr.Long;public static implicit operator ulong[](PropertyRepeatReader rr)=>rr.ULong;public static implicit operator double[](PropertyRepeatReader rr)=>rr.Double;public static implicit operator decimal[](PropertyRepeatReader rr)=>rr.Decimal;}public static class PRepeatEx{public static PropertyRepeatReader Repeat(this PropertyConsoleReader cr,int count)=>new PropertyRepeatReader(cr,count);}}
namespace Kzrnm.Competitive{using static MethodImplOptions;public static class __ArrayExtension{[MethodImpl(AggressiveInlining)]public static T[]Fill<T>(this T[]arr,T value){arr.AsSpan().Fill(value);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr){Array.Sort(arr);return arr;}[MethodImpl(AggressiveInlining)]public static string[]Sort(this string[]arr)=>Sort(arr,StringComparer.Ordinal);[MethodImpl(AggressiveInlining)]public static T[]Sort<T,U>(this T[]arr,Func<T,U>selector)where U:IComparable<U>{Array.Sort(arr.Select(selector).ToArray(),arr);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr,Comparison<T>comparison){Array.Sort(arr,comparison);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr,IComparer<T>comparer){Array.Sort(arr,comparer);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Reverse<T>(this T[]arr){Array.Reverse(arr);return arr;}[MethodImpl(AggressiveInlining)]public static ref T Get<T>(this T[]arr,int index){if(index<0)index+=arr.Length;return ref arr[index];}[MethodImpl(AggressiveInlining)]public static ref readonly T GetOrDummy<T>(this ReadOnlySpan<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this Span<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[]arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[][]arr,int index1,int index2,T dummy=default){if((uint)index1<(uint)arr.Length&&(uint)index2<(uint)arr[index1].Length)return ref arr[index1][index2];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[][][]arr,int index1,int index2,int index3,T dummy=default){if((uint)index1<(uint)arr.Length&&(uint)index2<(uint)arr[index1].Length&&(uint)index3<(uint)arr[index1][index2].Length)return ref arr[index1][index2][index3];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}private static class Dummy<T>{public static T dummy;}}}
internal partial class Program{static void Main()=>new Program(new PropertyConsoleReader(),new ConsoleWriter()).Run();public PropertyConsoleReader cr;public ConsoleWriter cw;public Program(PropertyConsoleReader r,ConsoleWriter w){this.cr=r;this.cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){var sw=cw.StreamWriter;int Q=__ManyTestCases?cr.Int:1;for(;Q>0;Q--){var res=Calc();if(res is double d)sw.WriteLine(d.ToString("0.####################",CultureInfo.InvariantCulture));else if(res is bool b)sw.WriteLine(YesNo(b));else if(res is char[]chrs)sw.WriteLine(chrs);else if(res!=null&&res!=cw)sw.WriteLine(res.ToString());}cw.Flush();}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander

提出情報

ジャッジ結果