Submission #20515210


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 A - Code
User naminodarie
Language C# (.NET Core 3.1.201)
Score 100
Code Size 42024 Byte
Status AC
Exec Time 937 ms
Memory 30692 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 01 Set 02 Set 03 Set 04 Set 05 Set 06 Set 07 Set 08 Set 09 Set 10
Score / Max Score 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10
Status
AC × 3
AC × 4
AC × 3
AC × 4
AC × 3
AC × 4
AC × 4
AC × 3
AC × 3
AC × 3
Set Name Test Cases
Set 01 01-01, 01-02, 01-03
Set 02 02-01, 02-02, 02-03, 02-04
Set 03 03-01, 03-02, 03-03
Set 04 04-01, 04-02, 04-03, 04-04
Set 05 05-01, 05-02, 05-03
Set 06 06-01, 06-02, 06-03, 06-04
Set 07 07-01, 07-02, 07-03, 07-04
Set 08 08-01, 08-02, 08-03
Set 09 09-01, 09-02, 09-03
Set 10 10-01, 10-02, 10-03
Case Name Status Exec Time Memory
01-01 AC 81 ms 27156 KB
01-02 AC 80 ms 26836 KB
01-03 AC 83 ms 26880 KB
02-01 AC 83 ms 26912 KB
02-02 AC 83 ms 26804 KB
02-03 AC 85 ms 26852 KB
02-04 AC 87 ms 26936 KB
03-01 AC 85 ms 26828 KB
03-02 AC 92 ms 26788 KB
03-03 AC 86 ms 26984 KB
04-01 AC 83 ms 27076 KB
04-02 AC 85 ms 27000 KB
04-03 AC 89 ms 26984 KB
04-04 AC 89 ms 27152 KB
05-01 AC 110 ms 27616 KB
05-02 AC 101 ms 27548 KB
05-03 AC 140 ms 27436 KB
06-01 AC 92 ms 27196 KB
06-02 AC 135 ms 28144 KB
06-03 AC 139 ms 28076 KB
06-04 AC 231 ms 28176 KB
07-01 AC 83 ms 27116 KB
07-02 AC 292 ms 28472 KB
07-03 AC 201 ms 28552 KB
07-04 AC 315 ms 28668 KB
08-01 AC 85 ms 27772 KB
08-02 AC 385 ms 30420 KB
08-03 AC 532 ms 30560 KB
09-01 AC 472 ms 30484 KB
09-02 AC 399 ms 30564 KB
09-03 AC 937 ms 30692 KB
10-01 AC 383 ms 30600 KB
10-02 AC 626 ms 30516 KB
10-03 AC 936 ms 30572 KB