Submission #20515221


Source Code Expand

Copy
using AtCoder.Internal;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using ModInt = AtCoder.StaticModInt<AtCoder.Mod1000000007>;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics.X86;
using System.Text;
using static Kzrnm.Competitive.Global;
partial class Program
{
    partial void WriteBool(bool b) => cw.WriteLine(b ? "Yes" : "No");
    bool __ManyTestCases() => false;
    [MethodImpl(MethodImplOptions.AggressiveOptimization)]
    private object Calc()
    {
        int R = cr;
        int C = cr;
        var grid = Grid.Create(cr.Repeat(R).Ascii);
        var dp = NewArray(2, R + C + 1, R + C + 1, default(ModInt));
        dp[0][0][0] = 4;
        ModInt res = 4;
        for (int d = 1; d < R + C; d++)
        {
            var t1 = d & 1;
            var t2 = t1 ^ 1;

            for (int tx = 0; tx <= d; tx++)
            {
                var ty = d - tx;
                if (tx >= C || ty >= R) continue;

                for (int dx = 0; dx <= d; dx++)
                {
                    var dy = d - dx;
                    if (dx >= C || dy >= R) continue;
                    dp[t1][tx][dx] = 0;
                    if (grid[ty, tx] != grid[dy, dx]) continue;
                    if (ty > 0)
                    {
                        var m = (tx == C - 1) ? 2 : 1;
                        if (dy > 0) dp[t1][tx][dx] += m * dp[t2][tx][dx];
                        if (dx > 0) dp[t1][tx][dx] += m * dp[t2][tx][dx - 1];
                    }
                    if (tx > 0)
                    {
                        var m = (ty == R - 1) ? 2 : 1;
                        if (dy > 0) dp[t1][tx][dx] += m * dp[t2][tx - 1][dx];
                        if (dx > 0) dp[t1][tx][dx] += m * dp[t2][tx - 1][dx - 1];
                    }
                    res = dp[t1][tx][dx];
                }

            }
        }

        return res;
    }
}
#region Expanded by https://github.com/naminodarie/SourceExpander
//LICENSE: https://github.com/naminodarie/Kzrnm.Competitive/blob/master/LICENSE
namespace AtCoder{using static MethodImplOptions;public interface IStaticMod{uint Mod{get;}bool IsPrime{get;}}public readonly struct Mod1000000007:IStaticMod{public uint Mod=>1000000007;public bool IsPrime=>true;}public readonly struct Mod998244353:IStaticMod{public uint Mod=>998244353;public bool IsPrime=>true;}public readonly struct StaticModIntOperator<T>:IArithmeticOperator<StaticModInt<T>>where T:struct,IStaticMod{public StaticModInt<T>MultiplyIdentity=>StaticModInt<T>.Raw(1);[MethodImpl(AggressiveInlining)]public StaticModInt<T>Add(StaticModInt<T>x,StaticModInt<T>y)=>x+y;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Subtract(StaticModInt<T>x,StaticModInt<T>y)=>x-y;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Multiply(StaticModInt<T>x,StaticModInt<T>y)=>x*y;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Divide(StaticModInt<T>x,StaticModInt<T>y)=>x/y;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Modulo(StaticModInt<T>x,StaticModInt<T>y)=>throw new NotSupportedException();[MethodImpl(AggressiveInlining)]public StaticModInt<T>Minus(StaticModInt<T>x)=>-x;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Increment(StaticModInt<T>x)=> ++x;[MethodImpl(AggressiveInlining)]public StaticModInt<T>Decrement(StaticModInt<T>x)=> --x;}public readonly struct StaticModInt<T>:IEquatable<StaticModInt<T>>where T:struct,IStaticMod{internal readonly uint _v;private static readonly T op=default;public int Value=>(int)_v;public static int Mod=>(int)op.Mod;[MethodImpl(AggressiveInlining)]public static StaticModInt<T>Raw(int v){var u=unchecked((uint)v);return new StaticModInt<T>(u);}public StaticModInt(long v):this(Round(v)){}private StaticModInt(uint v)=>_v=v;[MethodImpl(AggressiveInlining)]private static uint Round(long v){var x=v%op.Mod;if(x<0){x+=op.Mod;}return(uint)x;}[MethodImpl(AggressiveInlining)]public static StaticModInt<T>operator ++(StaticModInt<T>value){var v=value._v+1;if(v==op.Mod){v=0;}return new StaticModInt<T>(v);}[MethodImpl(AggressiveInlining)]public static StaticModInt<T>operator --(StaticModInt<T>value){var v=value._v;if(v==0){v=op.Mod;}return new StaticModInt<T>(v-1);}[MethodImpl(AggressiveInlining)]public static StaticModInt<T>operator+(StaticModInt<T>lhs,StaticModInt<T>rhs){var v=lhs._v+rhs._v;if(v>=op.Mod){v-=op.Mod;}return new StaticModInt<T>(v);}[MethodImpl(AggressiveInlining)]public static StaticModInt<T>operator-(StaticModInt<T>lhs,StaticModInt<T>rhs){unchecked{var v=lhs._v-rhs._v;if(v>=op.Mod){v+=op.Mod;}return new StaticModInt<T>(v);}}[MethodImpl(AggressiveInlining)]public static StaticModInt<T>operator*(StaticModInt<T>lhs,StaticModInt<T>rhs){return new StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));}public static StaticModInt<T>operator/(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs*rhs.Inv();public static StaticModInt<T>operator+(StaticModInt<T>value)=>value;public static StaticModInt<T>operator-(StaticModInt<T>value)=>new StaticModInt<T>(op.Mod-value._v);public static bool operator==(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v==rhs._v;public static bool operator!=(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v!=rhs._v;public static implicit operator StaticModInt<T>(int value)=>new StaticModInt<T>(value);public static implicit operator StaticModInt<T>(long value)=>new StaticModInt<T>(value);public StaticModInt<T>Pow(long n){var x=this;var r=new StaticModInt<T>(1U);while(n>0){if((n&1)>0){r*=x;}x*=x;n>>=1;}return r;}[MethodImpl(AggressiveInlining)]public StaticModInt<T>Inv(){if(op.IsPrime){return Pow(op.Mod-2);}else{var(g,x)=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 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{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 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 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{public static class Global{public static T[]NewArray<T>(int len0,T value)where T:struct=>new T[len0].Fill(value);public static T[]NewArray<T>(int len0,Func<T>factory){var arr=new T[len0];for(int i=0;i<arr.Length;i++)arr[i]=factory();return arr;}public static T[][]NewArray<T>(int len0,int len1,T value)where T:struct{var arr=new T[len0][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,value);return arr;}public static T[][]NewArray<T>(int len0,int len1,Func<T>factory){var arr=new T[len0][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,factory);return arr;}public static T[][][]NewArray<T>(int len0,int len1,int len2,T value)where T:struct{var arr=new T[len0][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,value);return arr;}public static T[][][]NewArray<T>(int len0,int len1,int len2,Func<T>factory){var arr=new T[len0][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,factory);return arr;}public static T[][][][]NewArray<T>(int len0,int len1,int len2,int len3,T value)where T:struct{var arr=new T[len0][][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,len3,value);return arr;}public static T[][][][]NewArray<T>(int len0,int len1,int len2,int len3,Func<T>factory){var arr=new T[len0][][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,len3,factory);return arr;}}}
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(){int Q=1;if(__ManyTestCases())Q=cr;for(;Q>0;Q--){var res=Calc();if(res is double d)cw.WriteLine(d.ToString("0.####################",CultureInfo.InvariantCulture));else if(res is bool b)WriteBool(b);else if(res!=null)cw.WriteLine(res.ToString());}cw.Flush();}partial void WriteBool(bool b);object Calc(Program dum=null)=>dum;bool __ManyTestCases(Program dum=null)=>false;}
namespace Kzrnm.Competitive{using static MethodImplOptions;public static class Grid{public static Grid<char>GridString(this PropertyConsoleReader cr,int H)=>Create(cr.Repeat(H).Ascii);public static Grid<char>GridString(this PropertyConsoleReader cr,int H,char defaultValue)=>Create(cr.Repeat(H).Ascii,defaultValue);public static Grid<int>GridInt(this PropertyConsoleReader cr,int H,int W)=>Create(cr.Repeat(H).Select(cr=>cr.Repeat(W).Int));public static Grid<int>GridInt(this PropertyConsoleReader cr,int H,int W,int defaultValue)=>Create(cr.Repeat(H).Select(cr=>cr.Repeat(W).Int),defaultValue);public static Grid<char>Create(string[]data)=>new Grid<char>(data.Flatten(),data.Length,data[0].Length,default(char));public static Grid<char>Create(string[]data,char defaultValue)=>new Grid<char>(data.Flatten(),data.Length,data[0].Length,defaultValue);public static Grid<T>Create<T>(T[][]data)=>new Grid<T>(data.Flatten(),data.Length,data[0].Length,default(T));public static Grid<T>Create<T>(T[][]data,T defaultValue)=>new Grid<T>(data.Flatten(),data.Length,data[0].Length,defaultValue);public static Grid<T>Create<T>(Span<T[]>data)=>new Grid<T>(data.Flatten(),data.Length,data[0].Length,default(T));public static Grid<T>Create<T>(Span<T[]>data,T defaultValue)=>new Grid<T>(data.Flatten(),data.Length,data[0].Length,defaultValue);public static Grid<T>Create<T>(ReadOnlySpan<T[]>data)=>new Grid<T>(data.Flatten(),data.Length,data[0].Length,default(T));public static Grid<T>Create<T>(ReadOnlySpan<T[]>data,T defaultValue)=>new Grid<T>(data.Flatten(),data.Length,data[0].Length,defaultValue);public static void WriteGrid(this Grid<char>grid,ConsoleWriter cw){for(int i=0;i<grid.H;i++)cw.StreamWriter.WriteLine(grid.data.AsSpan(i*grid.W,grid.W));}public static void WriteGrid<T>(this Grid<T>grid,ConsoleWriter cw){for(int i=0;i<grid.H;i++)cw.WriteLineJoin(grid.data.AsSpan(i*grid.W,grid.W));}}public class Grid<T>{public int Size=>data.Length;public readonly int H;public readonly int W;internal readonly T[]data;private readonly T defaultValue;public Grid(int H,int W,T defaultValue=default(T)):this(new T[H*W].Fill(defaultValue),H,W,defaultValue){}internal Grid(T[]data,int H,int W,T defaultValue){this.H=H;this.W=W;this.data=data;this.defaultValue=defaultValue;}[MethodImpl(AggressiveInlining)]public int Index(int h,int w)=>h*W+w;[MethodImpl(AggressiveInlining)]public(int h,int w)FromIndex(int ix){var h=ix/W;return(h,ix-h*W);}private T defaultReference;[MethodImpl(AggressiveInlining)]private ref T DefaultValueReference(){defaultReference=defaultValue;return ref defaultReference;}public ref T this[int h,int w]{[MethodImpl(AggressiveInlining)]get{if((uint)h<(uint)H&&(uint)w<(uint)W)return ref data[Index(h,w)];return ref DefaultValueReference();}}private class DebugLine{private T[]line;public DebugLine(T[]line){this.line=line;}public override string ToString(){if(line is char[]chrs)return new string(chrs);return string.Join(", ",line);}}private class DebugView{private readonly Grid<T>grid;public DebugView(Grid<T>grid){this.grid=grid;}public DebugLine[]Items{get{var items=new DebugLine[grid.H];for(int h=0;h<grid.H;h++){var line=new T[grid.W];for(int w=0;w<grid.W;w++)line[w]=grid[h,w];items[h]=new DebugLine(line);}return items;}}}}}
namespace AtCoder{public interface IAdditionOperator<T>{T Add(T x,T y);T Subtract(T x,T y);}public interface IMultiplicationOperator<T>{T Multiply(T x,T y);T MultiplyIdentity{get;}}public interface IDivisionOperator<T>:IMultiplicationOperator<T>{T Divide(T x,T y);T Modulo(T x,T y);}public interface IUnaryNumOperator<T>{T Minus(T x);T Increment(T x);T Decrement(T x);}public interface IArithmeticOperator<T>:IAdditionOperator<T>,IMultiplicationOperator<T>,IDivisionOperator<T>,IUnaryNumOperator<T>{}public interface ICompareOperator<T>:IComparer<T>{bool GreaterThan(T x,T y);bool GreaterThanOrEqual(T x,T y);bool LessThan(T x,T y);bool LessThanOrEqual(T x,T y);}public interface INumOperator<T>:IArithmeticOperator<T>,ICompareOperator<T>{T MinValue{get;}T MaxValue{get;}}public interface IShiftOperator<T>{T LeftShift(T x,int y);T RightShift(T x,int y);}}
namespace AtCoder.Internal{public static partial class InternalMath{private static readonly Dictionary<int,int>primitiveRootsCache=new Dictionary<int,int>(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};public static int PrimitiveRoot(int m){if(primitiveRootsCache.TryGetValue(m,out var p)){return p;}return primitiveRootsCache[m]=PrimitiveRootCalculate(m);}static int PrimitiveRootCalculate(int m){Span<int>divs=stackalloc int[20];divs[0]=2;int cnt=1;int x=(m-1)/2;while(x%2==0){x>>=1;}for(int i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;while(x%i==0){x/=i;}}}if(x>1){divs[cnt++]=x;}for(int g=2;;g++){bool ok=true;for(int i=0;i<cnt;i++){if(MathLib.PowMod(g,(m-1)/divs[i],m)==1){ok=false;break;}}if(ok){return g;}}}public static(long,long)InvGCD(long a,long b){a=SafeMod(a,b);if(a==0)return(b,0);long s=b,t=a;long m0=0,m1=1;long u;while(true){if(t==0){if(m0<0)m0+=b/s;return(s,m0);}u=s/t;s-=t*u;m0-=m1*u;if(s==0){if(m1<0)m1+=b/t;return(t,m1);}u=t/s;t-=s*u;m1-=m0*u;}}public static long SafeMod(long x,long m){x%=m;if(x<0)x+=m;return x;}public static bool IsPrime(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long d=n-1;while(d%2==0)d/=2;ReadOnlySpan<long>bases=stackalloc long[3]{2,7,61};foreach(long a in bases){long t=d;long y=MathLib.PowMod(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0){return false;}}return true;}}}
namespace 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 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 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{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,Expression<Func<T,U>>selector)where U:IComparable<U> =>Sort(arr,ExComparer<T>.CreateExp(selector));[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)return ref arr[arr.Length+index];return ref arr[index];}[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;}}}
namespace Kzrnm.Competitive.IO{public static class PropertyRepeatReaderSelect{public static T[]Select<T>(this PropertyRepeatReader r,Func<PropertyConsoleReader,T>factory){var arr=new T[r.count];for(var i=0;i<r.count;i++)arr[i]=factory(r.cr);return arr;}public static T[]Select<T>(this PropertyRepeatReader r,Func<PropertyConsoleReader,int,T>factory){var arr=new T[r.count];for(var i=0;i<r.count;i++)arr[i]=factory(r.cr,i);return arr;}}}
namespace System{using static MethodImplOptions;public static class __CollectionExtension{private class ArrayVal<T>{public T[]arr;}[MethodImpl(AggressiveInlining)]public static Span<T>AsSpan<T>(this List<T>list,int start=0)=>Unsafe.As<ArrayVal<T>>(list).arr.AsSpan(start,list.Count);[MethodImpl(AggressiveInlining)]public static TValue Get<TKey,TValue>(this IDictionary<TKey,TValue>dic,TKey key){dic.TryGetValue(key,out var v);return v;}public static(T Value,int Count)[]CompressCount<T>(this IEnumerable<T>collection){var e=collection.GetEnumerator();var list=new SimpleList<(T Value,int Count)>();if(!e.MoveNext())return Array.Empty<(T,int)>();var cur=e.Current;list.Add((cur,1));while(e.MoveNext()){if(EqualityComparer<T>.Default.Equals(cur,e.Current))list[^1].Count++;else{cur=e.Current;list.Add((cur,1));}}return list.ToArray();}public static T[]Flatten<T>(this T[][]array)=>Flatten((ReadOnlySpan<T[]>)array);public static T[]Flatten<T>(this Span<T[]>span)=>Flatten((ReadOnlySpan<T[]>)span);public static T[]Flatten<T>(this ReadOnlySpan<T[]>span){var res=new T[span.Length*span[0].Length];for(int i=0;i<span.Length;i++)for(int j=0;j<span[i].Length;j++)res[i*span[i].Length+j]=span[i][j];return res;}public static T[]Flatten<T>(this IList<IList<T>>collection){var res=new T[collection.Count*collection[0].Count];for(int i=0;i<collection.Count;i++)for(int j=0;j<collection[i].Count;j++)res[i*collection[i].Count+j]=collection[i][j];return res;}public static char[]Flatten(this string[]strs){var res=new char[strs.Length*strs[0].Length];for(int i=0;i<strs.Length;i++)for(int j=0;j<strs[i].Length;j++)res[i*strs[i].Length+j]=strs[i][j];return res;}}}
namespace AtCoder{public static class MathLib{public static int[]Convolution(int[]a,int[]b)=>Convolution<Mod998244353>(a,b);public static uint[]Convolution(uint[]a,uint[]b)=>Convolution<Mod998244353>(a,b);public static long[]Convolution(long[]a,long[]b)=>Convolution<Mod998244353>(a,b);public static ulong[]Convolution(ulong[]a,ulong[]b)=>Convolution<Mod998244353>(a,b);public static int[]Convolution<TMod>(int[]a,int[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<int>();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive<TMod>(a.Select(ai=>new StaticModInt<TMod>(ai)).ToArray(),b.Select(bi=>new StaticModInt<TMod>(bi)).ToArray());return c.Select(ci=>ci.Value).ToArray();}else{int z=1<<InternalBit.CeilPow2(n+m-1);var aTemp=new StaticModInt<TMod>[z];for(int i=0;i<a.Length;i++){aTemp[i]=new StaticModInt<TMod>(a[i]);}var bTemp=new StaticModInt<TMod>[z];for(int i=0;i<b.Length;i++){bTemp[i]=new StaticModInt<TMod>(b[i]);}var c=Convolution<TMod>(aTemp,bTemp,n,m,z).Slice(0,n+m-1);var result=new int[c.Length];for(int i=0;i<result.Length;i++){result[i]=c[i].Value;}return result;}}public static uint[]Convolution<TMod>(uint[]a,uint[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<uint>();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive<TMod>(a.Select(ai=>new StaticModInt<TMod>(ai)).ToArray(),b.Select(bi=>new StaticModInt<TMod>(bi)).ToArray());return c.Select(ci=>(uint)ci.Value).ToArray();}else{int z=1<<InternalBit.CeilPow2(n+m-1);var aTemp=new StaticModInt<TMod>[z];for(int i=0;i<a.Length;i++){aTemp[i]=new StaticModInt<TMod>(a[i]);}var bTemp=new StaticModInt<TMod>[z];for(int i=0;i<b.Length;i++){bTemp[i]=new StaticModInt<TMod>(b[i]);}var c=Convolution<TMod>(aTemp,bTemp,n,m,z).Slice(0,n+m-1);var result=new uint[c.Length];for(int i=0;i<result.Length;i++){result[i]=(uint)c[i].Value;}return result;}}public static long[]Convolution<TMod>(long[]a,long[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<long>();}if(Math.Min(n,m)<=60){var c=ConvolutionNaive<TMod>(a.Select(ai=>new StaticModInt<TMod>(ai)).ToArray(),b.Select(bi=>new StaticModInt<TMod>(bi)).ToArray());return c.Select(ci=>(long)ci.Value).ToArray();}else{int z=1<<InternalBit.CeilPow2(n+m-1);var aTemp=new StaticModInt<TMod>[z];for(int i=0;i<a.Length;i++){aTemp[i]=new StaticModInt<TMod>(a[i]);}var bTemp=new StaticModInt<TMod>[z];for(int i=0;i<b.Length;i++){bTemp[i]=new StaticModInt<TMod>(b[i]);}var c=Convolution<TMod>(aTemp,bTemp,n,m,z).Slice(0,n+m-1);var result=new long[c.Length];for(int i=0;i<result.Length;i++){result[i]=c[i].Value;}return result;}}public static ulong[]Convolution<TMod>(ulong[]a,ulong[]b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<ulong>();}if(Math.Min(n,m)<=60){Func<ulong,StaticModInt<TMod>>takeMod=x=>StaticModInt<TMod>.Raw((int)(x%default(TMod).Mod));var c=ConvolutionNaive<TMod>(a.Select(takeMod).ToArray(),b.Select(takeMod).ToArray());return c.Select(ci=>(ulong)ci.Value).ToArray();}else{int z=1<<InternalBit.CeilPow2(n+m-1);var aTemp=new StaticModInt<TMod>[z];for(int i=0;i<a.Length;i++){aTemp[i]=StaticModInt<TMod>.Raw((int)(a[i]%default(TMod).Mod));}var bTemp=new StaticModInt<TMod>[z];for(int i=0;i<b.Length;i++){bTemp[i]=StaticModInt<TMod>.Raw((int)(b[i]%default(TMod).Mod));}var c=Convolution<TMod>(aTemp,bTemp,n,m,z).Slice(0,n+m-1);var result=new ulong[c.Length];for(int i=0;i<result.Length;i++){result[i]=(ulong)c[i].Value;}return result;}}public static StaticModInt<TMod>[]Convolution<TMod>(StaticModInt<TMod>[]a,StaticModInt<TMod>[]b)where TMod:struct,IStaticMod{var temp=Convolution((ReadOnlySpan<StaticModInt<TMod>>)a,b);return temp.ToArray();}public static Span<StaticModInt<TMod>>Convolution<TMod>(ReadOnlySpan<StaticModInt<TMod>>a,ReadOnlySpan<StaticModInt<TMod>>b)where TMod:struct,IStaticMod{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<StaticModInt<TMod>>();}if(Math.Min(n,m)<=60){return ConvolutionNaive(a,b);}int z=1<<InternalBit.CeilPow2(n+m-1);var aTemp=new StaticModInt<TMod>[z];a.CopyTo(aTemp);var bTemp=new StaticModInt<TMod>[z];b.CopyTo(bTemp);return Convolution(aTemp.AsSpan(),bTemp.AsSpan(),n,m,z);}private static Span<StaticModInt<TMod>>Convolution<TMod>(Span<StaticModInt<TMod>>a,Span<StaticModInt<TMod>>b,int n,int m,int z)where TMod:struct,IStaticMod{Butterfly<TMod>.Calculate(a);Butterfly<TMod>.Calculate(b);for(int i=0;i<a.Length;i++){a[i]*=b[i];}Butterfly<TMod>.CalculateInv(a);var result=a.Slice(0,n+m-1);var iz=new StaticModInt<TMod>(z).Inv();foreach(ref var r in result){r*=iz;}return result;}public static long[]ConvolutionLong(ReadOnlySpan<long>a,ReadOnlySpan<long>b){unchecked{var n=a.Length;var m=b.Length;if(n==0||m==0){return Array.Empty<long>();}const ulong Mod1=754974721;const ulong Mod2=167772161;const ulong Mod3=469762049;const ulong M2M3=Mod2*Mod3;const ulong M1M3=Mod1*Mod3;const ulong M1M2=Mod1*Mod2;const ulong M1M2M3=Mod1*Mod2*Mod3;ulong i1=(ulong)InternalMath.InvGCD((long)M2M3,(long)Mod1).Item2;ulong i2=(ulong)InternalMath.InvGCD((long)M1M3,(long)Mod2).Item2;ulong i3=(ulong)InternalMath.InvGCD((long)M1M2,(long)Mod3).Item2;var c1=Convolution<FFTMod1>(a,b);var c2=Convolution<FFTMod2>(a,b);var c3=Convolution<FFTMod3>(a,b);var c=new long[n+m-1];Span<ulong>offset=stackalloc ulong[]{0,0,M1M2M3,2*M1M2M3,3*M1M2M3};for(int i=0;i<c.Length;i++){ulong x=0;x+=(c1[i]*i1)%Mod1*M2M3;x+=(c2[i]*i2)%Mod2*M1M3;x+=(c3[i]*i3)%Mod3*M1M2;long diff=(long)c1[i]-InternalMath.SafeMod((long)x,(long)Mod1);if(diff<0){diff+=(long)Mod1;}x-=offset[(int)(diff%offset.Length)];c[i]=(long)x;}return c;}}private static ulong[]Convolution<TMod>(ReadOnlySpan<long>a,ReadOnlySpan<long>b)where TMod:struct,IStaticMod{int z=1<<InternalBit.CeilPow2(a.Length+b.Length-1);var aTemp=new StaticModInt<TMod>[z];for(int i=0;i<a.Length;i++){aTemp[i]=new StaticModInt<TMod>(a[i]);}var bTemp=new StaticModInt<TMod>[z];for(int i=0;i<b.Length;i++){bTemp[i]=new StaticModInt<TMod>(b[i]);}var c=AtCoder.MathLib.Convolution<TMod>(aTemp,bTemp,a.Length,b.Length,z);var result=new ulong[c.Length];for(int i=0;i<result.Length;i++){result[i]=(ulong)c[i].Value;}return result;}private static StaticModInt<TMod>[]ConvolutionNaive<TMod>(ReadOnlySpan<StaticModInt<TMod>>a,ReadOnlySpan<StaticModInt<TMod>>b)where TMod:struct,IStaticMod{if(a.Length<b.Length){var temp=a;a=b;b=temp;}var ans=new StaticModInt<TMod>[a.Length+b.Length-1];for(int i=0;i<a.Length;i++){for(int j=0;j<b.Length;j++){ans[i+j]+=a[i]*b[j];}}return ans;}private readonly struct FFTMod1:IStaticMod{public uint Mod=>754974721;public bool IsPrime=>true;}private readonly struct FFTMod2:IStaticMod{public uint Mod=>167772161;public bool IsPrime=>true;}private readonly struct FFTMod3:IStaticMod{public uint Mod=>469762049;public bool IsPrime=>true;}public static long PowMod(long x,long n,int m){if(m==1)return 0;Barrett barrett=new Barrett((uint)m);uint r=1,y=(uint)InternalMath.SafeMod(x,m);while(0<n){if((n&1)!=0)r=barrett.Mul(r,y);y=barrett.Mul(y,y);n>>=1;}return r;}public static long InvMod(long x,long m){var(g,res)=InternalMath.InvGCD(x,m);return res;}public static(long 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);}public static long FloorSum(long n,long m,long a,long b){long ans=0;while(true){if(a>=m){ans+=(n-1)*n*(a/m)/2;a%=m;}if(b>=m){ans+=n*(b/m);b%=m;}long yMax=(a*n+b)/m;long xMax=yMax*m-b;if(yMax==0)return ans;ans+=(n-(xMax+a-1)/a)*yMax;(n,m,a,b)=(yMax,a,m,(a-xMax%a)%a);}}}}
namespace Kzrnm.Competitive{public static class ExComparer<T>{class ExpressionComparer<K>:IComparer<T>where K:IComparable<K>{private class ParameterReplaceVisitor:ExpressionVisitor{private readonly ParameterExpression from;private readonly ParameterExpression to;public ParameterReplaceVisitor(ParameterExpression from,ParameterExpression to){this.from=from;this.to=to;}protected override Expression VisitParameter(ParameterExpression node)=>node==from?to:base.VisitParameter(node);}readonly Comparison<T>func;public ExpressionComparer(Expression<Func<T,K>>expression){var paramA=expression.Parameters[0];var paramB=Expression.Parameter(typeof(T));var f2=(Expression<Func<T,K>>)new ParameterReplaceVisitor(expression.Parameters[0],paramB).Visit(expression);var compExp=Expression.Lambda<Comparison<T>>(Expression.Call(expression.Body,typeof(K).GetMethod(nameof(IComparable<K>.CompareTo),new[]{typeof(K)}),f2.Body),paramA,paramB);this.func=compExp.Compile();}public int Compare(T x,T y)=>func(x,y);public override bool Equals(object obj)=>obj is ExpressionComparer<K>c&&this.func==c.func;public override int GetHashCode()=>func.GetHashCode();}public static IComparer<T>CreateExp<K>(Expression<Func<T,K>>expression)where K:IComparable<K> =>new ExpressionComparer<K>(expression);}}
namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{private T[]data;private const int DefaultCapacity=2;public SimpleList(){data=new T[DefaultCapacity];}public SimpleList(int capacity){data=new T[Math.Max(capacity,DefaultCapacity)];}public SimpleList(IEnumerable<T>collection){if(collection is ICollection<T>col){data=new T[col.Count];col.CopyTo(data,0);Count=col.Count;}else{data=new T[DefaultCapacity];foreach(var item in collection)Add(item);}}public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[MethodImpl(MethodImplOptions.AggressiveInlining)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}public void Clear()=>Count=0;public bool Contains(T item)=>IndexOf(item)>=0;public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);public T[]ToArray()=>AsSpan().ToArray();bool ICollection<T>.IsReadOnly=>false;T IList<T>.this[int index]{get=>data[index];set=>data[index]=value;}T IReadOnlyList<T>.this[int index]{get=>data[index];}void IList<T>.Insert(int index,T item)=>throw new NotSupportedException();bool ICollection<T>.Remove(T item)=>throw new NotSupportedException();void IList<T>.RemoveAt(int index)=>throw new NotSupportedException();IEnumerator IEnumerable.GetEnumerator()=>((IEnumerable<T>)this).GetEnumerator();IEnumerator<T>IEnumerable<T>.GetEnumerator(){for(int i=0;i<Count;i++)yield return data[i];}public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}}
namespace AtCoder.Internal{using static MethodImplOptions;public static class InternalBit{[MethodImpl(AggressiveInlining)]public static int ExtractLowestSetBit(int n){if(Bmi1.IsSupported){return(int)Bmi1.ExtractLowestSetBit((uint)n);}return 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 static class Butterfly<T>where T:struct,IStaticMod{internal static readonly StaticModInt<T>[]sumE=CalcurateSumE();internal static readonly StaticModInt<T>[]sumIE=CalcurateSumIE();[MethodImpl(MethodImplOptions.AggressiveOptimization)]public static void Calculate(Span<StaticModInt<T>>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector<uint>.Count;var modV=new Vector<uint>(default(T).Mod);for(int ph=1;ph<=h;ph++){int w=1<<(ph-1);int p=1<<(h-ph);var now=StaticModInt<T>.Raw(1);for(int s=0;s<w;s++){int offset=s<<(h-ph+1);var ls=a.Slice(offset,p);var rs=a.Slice(offset+p,p);if(p<regLength){for(int i=0;i<p;i++){var l=ls[i];var r=rs[i]*now;ls[i]=l+r;rs[i]=l-r;}}else{foreach(ref var r in rs){r*=now;}var lu=MemoryMarshal.Cast<StaticModInt<T>,uint>(ls);var ru=MemoryMarshal.Cast<StaticModInt<T>,uint>(rs);for(int i=0;i<lu.Length;i+=regLength){var luSliced=lu.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(MethodImplOptions.AggressiveOptimization)]public static void CalculateInv(Span<StaticModInt<T>>a){var n=a.Length;var h=InternalBit.CeilPow2(n);var regLength=Vector<uint>.Count;var modV=new Vector<uint>(default(T).Mod);for(int ph=h;ph>=1;ph--){int w=1<<(ph-1);int p=1<<(h-ph);var iNow=StaticModInt<T>.Raw(1);for(int s=0;s<w;s++){int offset=s<<(h-ph+1);var ls=a.Slice(offset,p);var rs=a.Slice(offset+p,p);if(p<regLength){for(int i=0;i<p;i++){var l=ls[i];var r=rs[i];ls[i]=l+r;rs[i]=StaticModInt<T>.Raw((int)((ulong)(default(T).Mod+l.Value-r.Value)*(ulong)iNow.Value%default(T).Mod));}}else{var lu=MemoryMarshal.Cast<StaticModInt<T>,uint>(ls);var ru=MemoryMarshal.Cast<StaticModInt<T>,uint>(rs);for(int i=0;i<lu.Length;i+=regLength){var luSliced=lu.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((int)default(T).Mod);int cnt2=InternalBit.BSF(default(T).Mod-1);var e=new StaticModInt<T>(g).Pow((default(T).Mod-1)>>cnt2);var ie=e.Inv();var sumE=new StaticModInt<T>[30];Span<StaticModInt<T>>es=stackalloc StaticModInt<T>[cnt2-1];Span<StaticModInt<T>>ies=stackalloc StaticModInt<T>[cnt2-1];for(int i=es.Length-1;i>=0;i--){es[i]=e;ies[i]=ie;e*=e;ie*=ie;}var now=StaticModInt<T>.Raw(1);for(int i=0;i<=cnt2-2;i++){sumE[i]=es[i]*now;now*=ies[i];}return sumE;}private static StaticModInt<T>[]CalcurateSumIE(){int g=InternalMath.PrimitiveRoot((int)default(T).Mod);int cnt2=InternalBit.BSF(default(T).Mod-1);var e=new StaticModInt<T>(g).Pow((default(T).Mod-1)>>cnt2);var ie=e.Inv();var sumIE=new StaticModInt<T>[30];Span<StaticModInt<T>>es=stackalloc StaticModInt<T>[cnt2-1];Span<StaticModInt<T>>ies=stackalloc StaticModInt<T>[cnt2-1];for(int i=es.Length-1;i>=0;i--){es[i]=e;ies[i]=ie;e*=e;ie*=ie;}var now=StaticModInt<T>.Raw(1);for(int i=0;i<=cnt2-2;i++){sumIE[i]=ies[i]*now;now*=es[i];}return sumIE;}[Conditional("ATCODER_CONTRACT")]private static void CheckPow2(int n){if(BitOperations.PopCount((uint)n)!=1){throw new ArgumentException("配列長は2のべき乗でなければなりません。");}}}}
namespace AtCoder.Internal{public class Barrett{public uint Mod{get;private set;}internal readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1;}public uint Mul(uint a,uint b){ulong z=a;z*=b;if(Bmi2.X64.IsSupported){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);}}}
#endregion Expanded by https://github.com/naminodarie/SourceExpander

Submission Info

Submission Time
Task C - Mansion
User naminodarie
Language C# (.NET Core 3.1.201)
Score 0
Code Size 42024 Byte
Status RE
Exec Time 227 ms
Memory 45608 KB

Compile Error

Program.cs(83,127): warning CS0649: Field '__CollectionExtension.ArrayVal<T>.arr' is never assigned to, and will always have its default value null [/imojudge/csharp/csharp.csproj]

Judge Result

Set Name Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12 Set 13 Set 14 Set 15 Set 16 Set 17 Set 18 Set 19 Set 20 Set 21 Set 22 Set 23 Set 24 Set 25 Set 26 Set 27 Set 28 Set 29 Set 30 Set 31 Set 32 Set 33 Set 34 Set 35 Set 36 Set 37
Score / Max Score 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1 0 / 2 0 / 2 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 10
Status
RE × 6
RE × 2
RE × 4
RE × 5
RE × 2
RE × 3
RE × 6
RE × 5
RE × 5
RE × 5
RE × 4
RE × 3
RE × 8
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
WA × 2
RE × 1
WA × 1
RE × 1
RE × 4
RE × 2
RE × 3
RE × 2
RE × 4
RE × 4
RE × 9
RE × 2
RE × 2
RE × 3
RE × 2
RE × 3
RE × 3
Set Name Test Cases
Set 1 sa01-01, sa01-02, sa01-03, sa01-04, sa01-05, sa01-06
Set 2 sa02-01, sa02-02
Set 3 sb01-01, sb01-02, sb01-03, sb01-04
Set 4 sb02-01, sb02-02, sb02-03, sb02-04, sb02-05
Set 5 sc01-01, sc01-02
Set 6 sc02-01, sc02-02, sc02-03
Set 7 sd01-01, sd01-02, sd01-03, sd01-04, sd01-05, sd01-06
Set 8 sd02-01, sd02-02, sd02-03, sd02-04, sd02-05
Set 9 se01-01, se01-02, se01-03, se01-04, se01-05
Set 10 se02-01, se02-02, se02-03, se02-04, se02-05
Set 11 sf01-01, sf01-02, sf01-03, sf01-04
Set 12 sf02-01, sf02-02, sf02-03
Set 13 sg01-01, sg01-02, sg01-03, sg01-04, sg01-05, sg01-06, sg01-07, sg01-08
Set 14 sh01-01
Set 15 sh02-01
Set 16 sh03-01
Set 17 sh04-01
Set 18 sh05-01
Set 19 sh06-01
Set 20 sh07-01
Set 21 sh08-01
Set 22 sh09-01
Set 23 sh10-01, sh10-02, sh10-03
Set 24 si01-01, si01-02
Set 25 la01-01, la01-02, la01-03, la01-04
Set 26 la02-01, la02-02
Set 27 lb01-01, lb01-02, lb01-03
Set 28 lb02-01, lb02-02
Set 29 lc01-01, lc01-02, lc01-03, lc01-04
Set 30 le01-01, le01-02, le01-03, le01-04
Set 31 lj01-01, lj01-02, lj01-03, lj01-04, lj01-05, lj01-06, lj01-07, lj01-08, lj01-09
Set 32 lh01-01, lh01-02
Set 33 lh02-01, lh02-02
Set 34 lh03-01, lh03-02, lh03-03
Set 35 lh04-01, lh04-02
Set 36 lh05-01, lh05-02, lh05-03
Set 37 li01-01, li01-02, li01-03
Case Name Status Exec Time Memory
la01-01 RE 219 ms 39704 KB
la01-02 RE 213 ms 31832 KB
la01-03 RE 199 ms 32072 KB
la01-04 RE 215 ms 31756 KB
la02-01 RE 194 ms 31756 KB
la02-02 RE 205 ms 31820 KB
lb01-01 RE 221 ms 45428 KB
lb01-02 RE 212 ms 33888 KB
lb01-03 RE 221 ms 33928 KB
lb02-01 RE 200 ms 31732 KB
lb02-02 RE 197 ms 31924 KB
lc01-01 RE 205 ms 34836 KB
lc01-02 RE 203 ms 31952 KB
lc01-03 RE 202 ms 31820 KB
lc01-04 RE 211 ms 32044 KB
le01-01 RE 206 ms 32044 KB
le01-02 RE 199 ms 31828 KB
le01-03 RE 197 ms 31756 KB
le01-04 RE 195 ms 32068 KB
lh01-01 RE 202 ms 31352 KB
lh01-02 RE 197 ms 31256 KB
lh02-01 RE 201 ms 31248 KB
lh02-02 RE 199 ms 31356 KB
lh03-01 RE 200 ms 31320 KB
lh03-02 RE 197 ms 31296 KB
lh03-03 RE 215 ms 36836 KB
lh04-01 RE 206 ms 38384 KB
lh04-02 RE 207 ms 31340 KB
lh05-01 RE 200 ms 32632 KB
lh05-02 RE 227 ms 45344 KB
lh05-03 RE 199 ms 31044 KB
li01-01 RE 226 ms 45424 KB
li01-02 RE 220 ms 41916 KB
li01-03 RE 196 ms 31124 KB
lj01-01 RE 198 ms 31468 KB
lj01-02 RE 200 ms 31248 KB
lj01-03 RE 198 ms 31472 KB
lj01-04 RE 197 ms 31180 KB
lj01-05 RE 202 ms 31332 KB
lj01-06 RE 196 ms 31336 KB
lj01-07 RE 200 ms 31488 KB
lj01-08 RE 199 ms 31336 KB
lj01-09 RE 223 ms 45608 KB
sa01-01 RE 207 ms 38380 KB
sa01-02 RE 197 ms 31212 KB
sa01-03 RE 204 ms 31252 KB
sa01-04 RE 200 ms 31352 KB
sa01-05 RE 203 ms 31260 KB
sa01-06 RE 202 ms 31252 KB
sa02-01 RE 199 ms 31296 KB
sa02-02 RE 202 ms 31332 KB
sb01-01 RE 214 ms 41116 KB
sb01-02 RE 206 ms 31368 KB
sb01-03 RE 201 ms 31180 KB
sb01-04 RE 202 ms 31376 KB
sb02-01 RE 207 ms 31244 KB
sb02-02 RE 204 ms 31168 KB
sb02-03 RE 197 ms 31328 KB
sb02-04 RE 197 ms 31244 KB
sb02-05 RE 205 ms 31484 KB
sc01-01 RE 209 ms 38252 KB
sc01-02 RE 206 ms 31148 KB
sc02-01 RE 199 ms 31260 KB
sc02-02 RE 197 ms 31176 KB
sc02-03 RE 194 ms 31468 KB
sd01-01 RE 211 ms 36832 KB
sd01-02 RE 202 ms 31244 KB
sd01-03 RE 200 ms 31392 KB
sd01-04 RE 216 ms 31396 KB
sd01-05 RE 202 ms 31492 KB
sd01-06 RE 200 ms 31248 KB
sd02-01 RE 201 ms 31260 KB
sd02-02 RE 194 ms 31408 KB
sd02-03 RE 208 ms 31252 KB
sd02-04 RE 198 ms 31332 KB
sd02-05 RE 200 ms 31256 KB
se01-01 RE 201 ms 31244 KB
se01-02 RE 205 ms 31376 KB
se01-03 RE 194 ms 31180 KB
se01-04 RE 199 ms 31380 KB
se01-05 RE 204 ms 31356 KB
se02-01 RE 213 ms 38384 KB
se02-02 RE 197 ms 31344 KB
se02-03 RE 221 ms 31244 KB
se02-04 RE 190 ms 31260 KB
se02-05 RE 194 ms 31356 KB
sf01-01 RE 201 ms 31264 KB
sf01-02 RE 198 ms 31464 KB
sf01-03 RE 199 ms 31144 KB
sf01-04 RE 208 ms 38296 KB
sf02-01 RE 206 ms 39768 KB
sf02-02 RE 202 ms 31256 KB
sf02-03 RE 197 ms 31260 KB
sg01-01 RE 200 ms 31244 KB
sg01-02 RE 196 ms 31248 KB
sg01-03 RE 200 ms 31208 KB
sg01-04 RE 204 ms 31508 KB
sg01-05 RE 202 ms 31324 KB
sg01-06 RE 210 ms 31300 KB
sg01-07 RE 199 ms 31180 KB
sg01-08 RE 201 ms 31184 KB
sh01-01 RE 216 ms 31344 KB
sh02-01 RE 194 ms 31212 KB
sh03-01 RE 199 ms 31252 KB
sh04-01 RE 202 ms 31472 KB
sh05-01 RE 217 ms 34616 KB
sh06-01 RE 209 ms 36988 KB
sh07-01 RE 205 ms 35528 KB
sh08-01 RE 217 ms 38500 KB
sh09-01 RE 208 ms 41964 KB
sh10-01 RE 224 ms 45412 KB
sh10-02 WA 79 ms 26800 KB
sh10-03 WA 87 ms 26884 KB
si01-01 RE 218 ms 45444 KB
si01-02 WA 83 ms 26792 KB