using AtCoder.Operators; using BitArray = System.Collections.BitArray; using Kzrnm.Competitive; using Kzrnm.Competitive.IO; using System; using System.Buffers; using System.Buffers.Text; using System.Collections; 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; using static Kzrnm.Competitive.Global; using 凾 = System.Runtime.CompilerServices.MethodImplAttribute; partial class Program { const bool __ManyTestCases = false; #if !LOCAL_RUNNING static void Main()=>new Program(new PropertyConsoleReader(),new Utf8ConsoleWriter()).Run(); [凾(256)] #endif private ConsoleOutput? Calc() { int N = cr; int M = cr; long T = cr; var bits = NewArray(N, () => new BitArray(N)); for (int i = 0; i < M; i++) { int a = cr; int b = cr; bits[a][b] = true; } return new BitOrMatrix(bits).Pow(T).Value[0].PopCount(); } } #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.Operators{public interface IAdditionOperator{T Add(T x,T y);}public interface ISubtractOperator{T Subtract(T x,T y);}public interface IMultiplicationOperator{T Multiply(T x,T y);T MultiplyIdentity{get;}}public interface IDivisionOperator:IMultiplicationOperator{T Divide(T x,T y);T Modulo(T x,T y);}public interface IUnaryNumOperator{T Minus(T x);T Increment(T x);T Decrement(T x);}public interface IArithmeticOperator:IAdditionOperator,ISubtractOperator,IMultiplicationOperator,IDivisionOperator,IUnaryNumOperator{}public interface ICompareOperator:IComparer{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 MinValue{get;}T MaxValue{get;}}public interface INumOperator:IArithmeticOperator,ICompareOperator,IMinMaxValue{}public interface IShiftOperator{T LeftShift(T x,int y);T RightShift(T x,int y);}} namespace AtCoder{public readonly struct LongOperator:INumOperator,IShiftOperator{public long MinValue=>long.MinValue;public long MaxValue=>long.MaxValue;public long MultiplyIdentity=>1L;[凾(256)]public long Add(long x,long y)=>x+y;[凾(256)]public long Subtract(long x,long y)=>x-y;[凾(256)]public long Multiply(long x,long y)=>x*y;[凾(256)]public long Divide(long x,long y)=>x/y;[凾(256)]public long Modulo(long x,long y)=>x%y;[凾(256)]public long Minus(long x)=>-x;[凾(256)]public long Increment(long x)=> ++x;[凾(256)]public long Decrement(long x)=> --x;[凾(256)]public bool GreaterThan(long x,long y)=>x>y;[凾(256)]public bool GreaterThanOrEqual(long x,long y)=>x>=y;[凾(256)]public bool LessThan(long x,long y)=>xx<=y;[凾(256)]public int Compare(long x,long y)=>x.CompareTo(y);[凾(256)]public long LeftShift(long x,int y)=>x<x>>y;}} namespace Kzrnm.Competitive.IO{using static Utf8Parser;using _R=ConsoleReader;public class ConsoleReader{internal const int BufSize=1<<12;internal readonly Stream input;internal readonly Encoding encoding;internal readonly byte[]buf;internal int pos;internal int len;[凾(256)]public ConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding,BufSize){}[凾(256)]public ConsoleReader(Stream input,Encoding encoding):this(input,encoding,BufSize){}[凾(256)]public ConsoleReader(Stream input,Encoding encoding,int bufferSize){this.input=input;this.encoding=encoding;buf=new byte[bufferSize];}[凾(256)]private void FillEntireNumber(){if((uint)pos>=(uint)buf.Length)FillNextBuffer();while(buf[pos]<=' ')if( ++pos>=len)FillNextBuffer();if(pos+21>=buf.Length&&buf[buf.Length-1]>' ')FillEntireNumberImpl();}private void FillEntireNumberImpl(){buf.AsSpan(pos,len-pos).CopyTo(buf);len-=pos;pos=0;var numberOfBytes=input.Read(buf,len,buf.Length-len);if(numberOfBytes==0)buf[len++]=10;else if(numberOfBytes+len=len)FillNextBuffer();return buf[pos++];}[凾(256)]public T Read(){if(typeof(T)==typeof(int))return(T)(object)Int();if(typeof(T)==typeof(uint))return(T)(object)UInt();if(typeof(T)==typeof(long))return(T)(object)Long();if(typeof(T)==typeof(ulong))return(T)(object)ULong();if(typeof(T)==typeof(double))return(T)(object)Double();if(typeof(T)==typeof(decimal))return(T)(object)Decimal();if(typeof(T)==typeof(char))return(T)(object)Char();if(typeof(T)==typeof(string))return(T)(object)Ascii();return Throw();}static T Throw()=>throw new NotSupportedException(typeof(T).Name);[凾(256)]public int Int(){FillEntireNumber();TryParse(buf.AsSpan(pos),out int v,out int bc);pos+=bc;return v;}[凾(256)]public uint UInt(){FillEntireNumber();TryParse(buf.AsSpan(pos),out uint v,out int bc);pos+=bc;return v;}[凾(256)]public long Long(){FillEntireNumber();TryParse(buf.AsSpan(pos),out long v,out int bc);pos+=bc;return v;}[凾(256)]public ulong ULong(){FillEntireNumber();TryParse(buf.AsSpan(pos),out ulong v,out int bc);pos+=bc;return v;}[凾(256)]public double Double(){FillEntireNumber();TryParse(buf.AsSpan(pos),out double v,out int bc);pos+=bc;return v;}[凾(256)]public decimal Decimal(){FillEntireNumber();TryParse(buf.AsSpan(pos),out decimal v,out int bc);pos+=bc;return v;}[凾(256)]public string String(){var sb=new List();;byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(' '();byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}[凾(256)]public char Char(){byte b;do b=ReadByte();while(b<=' ');return(char)b;}[凾(256)]public int Int0()=>Int()-1;[凾(256)]public uint UInt0()=>UInt()-1;[凾(256)]public long Long0()=>Long()-1;[凾(256)]public ulong ULong0()=>ULong()-1;[凾(256)]public static implicit operator int(_R cr)=>cr.Int();[凾(256)]public static implicit operator uint(_R cr)=>cr.UInt();[凾(256)]public static implicit operator long(_R cr)=>cr.Long();[凾(256)]public static implicit operator ulong(_R cr)=>cr.ULong();[凾(256)]public static implicit operator double(_R cr)=>cr.Double();[凾(256)]public static implicit operator decimal(_R cr)=>cr.Decimal();[凾(256)]public static implicit operator string(_R cr)=>cr.Ascii();public T[]Repeat(int count){var arr=new T[count];for(int i=0;i();return arr;}}} namespace Kzrnm.Competitive.IO{public sealed class PropertyConsoleReader:ConsoleReader{public PropertyConsoleReader():base(){}public PropertyConsoleReader(Stream input,Encoding encoding):base(input,encoding){}public PropertyConsoleReader(Stream input,Encoding encoding,int bufferSize):base(input,encoding,bufferSize){}public new int Int=>Int();public new int Int0=>Int0();public new uint UInt=>UInt();public new uint UInt0=>UInt0();public new long Long=>Long();public new long Long0=>Long0();public new ulong ULong=>ULong();public new ulong ULong0=>ULong0();public new double Double=>Double();public new decimal Decimal=>Decimal();public new string String=>String();public new string Ascii=>Ascii();public new string Line=>Line();public new char Char=>Char();}} namespace Kzrnm.Competitive.IO{using static Utf8Formatter;using _W=Utf8ConsoleWriter;public sealed class Utf8ConsoleWriter:IDisposable{internal static readonly UTF8Encoding Utf8NoBom=new UTF8Encoding(false);internal const int BufSize=1<<12;internal readonly Stream output;internal byte[]buf;internal int len;public Utf8ConsoleWriter():this(Console.OpenStandardOutput()){}public Utf8ConsoleWriter(Stream output):this(output,BufSize){}public Utf8ConsoleWriter(Stream output,int bufferSize){this.output=output;buf=new byte[bufferSize];}public StreamWriter ToStreamWriter(){Flush();return new StreamWriter(output,Utf8NoBom);}[凾(256)]public void Flush(){output.Write(buf,0,len);len=0;}void IDisposable.Dispose()=>Flush();[凾(256)]private SpanEnsureBuf(int size){if(buf.Length-len(T v){void FormatFloat(double d,out int b)=>TryFormat(d,EnsureBuf(Math.Max(25+(int)Math.Log10(Math.Abs(d)),32)),out b,new StandardFormat('F',20));void FormatDec(decimal d,out int b)=>TryFormat(d,EnsureBuf(Math.Max(25+(int)Math.Log10((double)Math.Abs(d)),32)),out b,new StandardFormat('F',20));int bw;if(typeof(T)==typeof(int))TryFormat((int)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(long))TryFormat((long)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(uint))TryFormat((uint)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(ulong))TryFormat((ulong)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(short))TryFormat((short)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(ushort))TryFormat((ushort)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(byte))TryFormat((byte)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(sbyte))TryFormat((sbyte)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(float))FormatFloat((float)(object)v,out bw);else if(typeof(T)==typeof(double))FormatFloat((double)(object)v,out bw);else if(typeof(T)==typeof(decimal))FormatDec((decimal)(object)v,out bw);else if(typeof(T)==typeof(char)){var dst=EnsureBuf(6);var c=(char)(object)v;if(c<0x007f){dst[0]=(byte)c;bw=1;}else{Spans=stackalloc char[1]{c};bw=Utf8NoBom.GetBytes(s,dst);}}else if(v is char[]charr)return Write(charr.AsSpan());else if(v is IUtf8ConsoleWriterFormatter f){f.Write(this);return this;}else return Write(v.ToString().AsSpan());len+=bw;return this;}[凾(256|512)]public _W Write(ReadOnlySpanv){var mlen=Utf8NoBom.GetMaxByteCount(v.Length);if(mlen>buf.Length){Flush();buf=new byte[mlen*2];}else if(mlen>buf.Length-len){Flush();}var bw=Utf8NoBom.GetBytes(v,buf.AsSpan(len));len+=bw;return this;}[凾(256)]public _W WriteLine()=>Write('\n');[凾(256)]public _W WriteLine(T v){Write(v);return Write('\n');}[凾(256)]public _W WriteLine(ReadOnlySpanv){Write(v);return Write('\n');}[凾(256)]public _W WriteLineJoin(IEnumerablecol)=>WriteMany(' ',col);[凾(256)]public _W WriteLineJoin((T1,T2)tuple){Write(tuple.Item1);Write(' ');return WriteLine(tuple.Item2);}[凾(256)]public _W WriteLineJoin((T1,T2,T3)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');return WriteLine(tuple.Item3);}[凾(256)]public _W WriteLineJoin((T1,T2,T3,T4)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');Write(tuple.Item3);Write(' ');return WriteLine(tuple.Item4);}[凾(256)]public _W WriteLineJoin(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;iWriteMany(' ',col);[凾(256)]public _W WriteLineJoin(T1 v1,T2 v2){Write(v1);Write(' ');return WriteLine(v2);}[凾(256)]public _W WriteLineJoin(T1 v1,T2 v2,T3 v3){Write(v1);Write(' ');Write(v2);Write(' ');return WriteLine(v3);}[凾(256)]public _W WriteLineJoin(T1 v1,T2 v2,T3 v3,T4 v4){Write(v1);Write(' ');Write(v2);Write(' ');Write(v3);Write(' ');return WriteLine(v4);}[凾(256)]public _W WriteLineJoin(params T[]col)=>WriteMany(' ',(ReadOnlySpan)col);[凾(256)]public _W WriteLineJoin(Spancol)=>WriteMany(' ',(ReadOnlySpan)col);[凾(256)]public _W WriteLineJoin(ReadOnlySpancol)=>WriteMany(' ',col);[凾(256)]public _W WriteLines(IEnumerablecol)=>WriteMany('\n',col);[凾(256)]public _W WriteLines(T[]col)=>WriteMany('\n',(ReadOnlySpan)col);[凾(256)]public _W WriteLines(Spancol)=>WriteMany('\n',(ReadOnlySpan)col);[凾(256)]public _W WriteLines(ReadOnlySpancol)=>WriteMany('\n',col);[凾(256)]public _W WriteGrid(IEnumerable>cols){foreach(var col in cols)WriteLineJoin(col);return this;}[凾(256)]public _W WriteGrid(IEnumerabletuples)where TTuple:ITuple{foreach(var tup in tuples)WriteLineJoin(tup);return this;}[凾(256)]private _W WriteMany(char sep,IEnumerablecol){if(col is T[]array)return WriteMany(sep,(ReadOnlySpan)array);var en=col.GetEnumerator();if(en.MoveNext()){Write(en.Current);while(en.MoveNext()){Write(sep);Write(en.Current);}}return WriteLine();}[凾(256)]private _W WriteMany(char sep,ReadOnlySpancol){if(col.Length>0){Write(col[0]);foreach(var c in col.Slice(1)){Write(sep);Write(c);}}return WriteLine();}}public interface IUtf8ConsoleWriterFormatter{void Write(_W cw);}} namespace Kzrnm.Competitive{using O=ConsoleOutput;public static class ConsoleOutputExt{[凾(256)]public static O ToConsoleOutput(this T f)where T:IUtf8ConsoleWriterFormatter{var cw=O.cw;f.Write(cw);return cw.WriteLine();}}public struct ConsoleOutput{public static Utf8ConsoleWriter cw;public static implicit operator O(int v)=>cw.WriteLine(v);public static implicit operator O(long v)=>cw.WriteLine(v);public static implicit operator O(uint v)=>cw.WriteLine(v);public static implicit operator O(ulong v)=>cw.WriteLine(v);public static implicit operator O(double v)=>cw.WriteLine(v);public static implicit operator O(decimal v)=>cw.WriteLine(v);public static implicit operator O(char v)=>cw.WriteLine(v);public static implicit operator O(ReadOnlySpanv)=>cw.WriteLine(v);public static implicit operator O(char[]v)=>cw.WriteLine((ReadOnlySpan)v);public static implicit operator O(string v)=>cw.WriteLine((ReadOnlySpan)v);public static implicit operator O(bool v)=>cw.WriteLine((ReadOnlySpan)(v?"Yes":"No"));public static implicit operator O(Utf8ConsoleWriter _)=>default;}} internal partial class Program{public PropertyConsoleReader cr;public Utf8ConsoleWriter cw;public Program(PropertyConsoleReader r,Utf8ConsoleWriter w){cr=r;ConsoleOutput.cw=cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){int Q=__ManyTestCases?cr.Int:1;while( --Q>=0)Calc();cw.Flush();}} namespace Kzrnm.Competitive{public static class Bit{[凾(256)]public static string ToBitString(this int num,int padLeft=sizeof(int)*8)=>Convert.ToString(num,2).PadLeft(padLeft,'0');[凾(256)]public static string ToBitString(this uint num,int padLeft=sizeof(uint)*8)=>Convert.ToString((int)num,2).PadLeft(padLeft,'0');[凾(256)]public static string ToBitString(this long num,int padLeft=sizeof(long)*8)=>Convert.ToString(num,2).PadLeft(padLeft,'0');[凾(256)]public static string ToBitString(this ulong num,int padLeft=sizeof(ulong)*8)=>Convert.ToString(unchecked((long)num),2).PadLeft(padLeft,'0');[凾(256)]public static bool On(this int num,int index)=>((num>>index)&1)!=0;[凾(256)]public static bool On(this uint num,int index)=>((num>>index)&1)!=0;[凾(256)]public static bool On(this long num,int index)=>((num>>index)&1)!=0;[凾(256)]public static bool On(this ulong num,int index)=>((num>>index)&1)!=0;[凾(256)]public static Enumerator Bits(this int num)=>new Enumerator(num);[凾(256)]public static Enumerator Bits(this uint num)=>new Enumerator(num);[凾(256)]public static Enumerator Bits(this long num)=>new Enumerator(num);[凾(256)]public static Enumerator Bits(this ulong num)=>new Enumerator(num);public struct Enumerator:IEnumerable,IEnumerator{ulong num;public Enumerator(int num):this((ulong)(uint)num){}public Enumerator(long num):this((ulong)num){}public Enumerator(ulong num){this.num=num;Current=-1;}public Enumerator GetEnumerator()=>this;public int Current{get;private set;}[凾(256)]public bool MoveNext(){if(num==0)return false;if(Bmi1.X64.IsSupported){Current=unchecked((int)Bmi1.X64.TrailingZeroCount(num));num=Bmi1.X64.ResetLowestSetBit(num);}else MoveNextLogical();return true;}void MoveNextLogical(){Current=BitOperations.TrailingZeroCount(num);num&=num-1;}object IEnumerator.Current=>Current;public int[]ToArray(){var res=new int[BitOperations.PopCount(num)];for(int i=0;ithrow new NotSupportedException();void IDisposable.Dispose(){}IEnumeratorIEnumerable.GetEnumerator()=>this;IEnumerator IEnumerable.GetEnumerator()=>this;}}} namespace Kzrnm.Competitive{public static class __ArrayExtension{[凾(256)]public static T[]Fill(this T[]arr,T value){arr.AsSpan().Fill(value);return arr;}[凾(256)]public static T[]Sort(this T[]arr){Array.Sort(arr);return arr;}[凾(256)]public static string[]Sort(this string[]arr)=>Sort(arr,StringComparer.Ordinal);[凾(256)]public static T[]Sort(this T[]arr,Funcselector)where U:IComparable{Array.Sort(arr.Select(selector).ToArray(),arr);return arr;}[凾(256)]public static T[]Sort(this T[]arr,Comparisoncomparison){Array.Sort(arr,comparison);return arr;}[凾(256)]public static T[]Sort(this T[]arr,IComparercomparer){Array.Sort(arr,comparer);return arr;}[凾(256)]public static T[]Reverse(this T[]arr){Array.Reverse(arr);return arr;}[凾(256)]public static ref T Get(this T[]arr,int index){if(index<0)index+=arr.Length;return ref arr[index];}[凾(256)]public static ref readonly T GetOrDummy(this ReadOnlySpanarr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy.dummy=dummy;return ref Dummy.dummy;}[凾(256)]public static ref T GetOrDummy(this Spanarr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy.dummy=dummy;return ref Dummy.dummy;}[凾(256)]public static ref T GetOrDummy(this T[]arr,int index,T dummy=default)=>ref GetOrDummy(arr.AsSpan(),index,dummy);[凾(256)]public static ref T GetOrDummy(this T[][]arr,int index1,int index2,T dummy=default){if((uint)index1<(uint)arr.Length)return ref GetOrDummy(arr[index1],index2,dummy);Dummy.dummy=dummy;return ref Dummy.dummy;}[凾(256)]public static ref T GetOrDummy(this T[][][]arr,int index1,int index2,int index3,T dummy=default){if((uint)index1<(uint)arr.Length)return ref GetOrDummy(arr[index1],index2,index3,dummy);Dummy.dummy=dummy;return ref Dummy.dummy;}private static class Dummy{public static T dummy;}[凾(256)]public static int FindByBinarySearch(this T[]arr,TCv value)where TCv:IComparable =>FindByBinarySearch((ReadOnlySpan)arr,value);[凾(256)]public static int FindByBinarySearch(this Spanarr,TCv value)where TCv:IComparable =>FindByBinarySearch((ReadOnlySpan)arr,value);[凾(256)]public static int FindByBinarySearch(this ReadOnlySpanarr,TCv value)where TCv:IComparable{int ix=arr.BinarySearch(value);if(ix<0)ix=~ix;return ix;}}} namespace Kzrnm.Competitive{public static class __BitArrayExtension{private class Dummy{public int[]arr;public int len;public int ver;}[凾(256)]public static int[]GetArray(this BitArray b)=>Unsafe.As(b).arr;[凾(256)]public static void CopyTo(this BitArray b,int[]array,int index=0)=>b.CopyTo((Array)array,index);[凾(256)]public static void CopyTo(this BitArray b,uint[]array,int index=0)=>b.CopyTo((Array)array,index);[凾(256)]public static void CopyTo(this BitArray b,bool[]array,int index=0)=>b.CopyTo((Array)array,index);[凾(256)]public static uint[]ToUInt32Array(this BitArray b){var arr=new uint[(b.Length+31)/32];b.CopyTo(arr);return arr;}[凾(256)]public static int[]OnBits(this BitArray b){var arr=b.GetArray();var brr=MemoryMarshal.Cast(arr);var l=new List(b.Length);for(var i=0;i=b.Length)break;l.Add(bb);}if((arr.Length&1)!=0)foreach(var bit in arr[^1].Bits()){var bb=bit+64*brr.Length;if(bb>=b.Length)break;l.Add(bb);}return l.AsSpan().ToArray();}[凾(256)]public static int PopCount(this BitArray b){var arr=b.GetArray().AsSpan();var rem=b.Length&31;int cnt=rem==0?0:-BitOperations.PopCount((uint)((-1<(arr);foreach(var bb in brr)cnt+=BitOperations.PopCount(bb);return cnt;}[凾(256)]public static int Lsb(this BitArray b){var arr=b.GetArray().AsSpan();var brr=MemoryMarshal.Cast(arr);for(int i=0;i(arr);for(int i=brr.Length-1;i>=0;i--)if(brr[i]!=0)return Math.Min(b.Length,BitOperations.Log2(brr[i])+i*64);return b.Length;}}} namespace Kzrnm.Competitive{public static class __MemoryMarshalExtension{private class ArrayVal{public T[]arr;}[凾(256)]public static SpanAsSpan(this Listlist,int start=0)=>Unsafe.As>(list).arr.AsSpan(start,list.Count-start);[凾(256)]public static SpanCast(this Spanspan)where TFrom:struct where TTo:struct=>MemoryMarshal.Cast(span);[凾(256)]public static ReadOnlySpanCast(this ReadOnlySpanspan)where TFrom:struct where TTo:struct=>MemoryMarshal.Cast(span);[凾(256)]public static ref T GetReference(this Spanspan)=>ref MemoryMarshal.GetReference(span);[凾(256)]public static ref T GetReference(this ReadOnlySpanspan)=>ref MemoryMarshal.GetReference(span);}} namespace Kzrnm.Competitive{public static class Global{[凾(256)]public static string YesNo(bool b)=>b?"Yes":"No";[凾(256)]public static string TakahashiAoki(bool b)=>b?"Takahashi":"Aoki";[凾(256)]public static T[]NewArray(int len0,T value)where T:struct=>new T[len0].Fill(value);[凾(256)]public static T[]NewArray(int len0,Funcfactory){var arr=new T[len0];for(int i=0;i(int len0,int len1,T value)where T:struct{var arr=new T[len0][];for(int i=0;i(int len0,int len1,Funcfactory){var arr=new T[len0][];for(int i=0;i(int len0,int len1,int len2,T value)where T:struct{var arr=new T[len0][][];for(int i=0;i(int len0,int len1,int len2,Funcfactory){var arr=new T[len0][][];for(int i=0;i(int len0,int len1,int len2,int len3,T value)where T:struct{var arr=new T[len0][][][];for(int i=0;i(int len0,int len1,int len2,int len3,Funcfactory){var arr=new T[len0][][][];for(int i=0;i(T x,long y)where TOp:struct,IMultiplicationOperator{var op=new TOp();T res=((y&1)!=0)?x:op.MultiplyIdentity;for(y>>=1;y>0;y>>=1){x=op.Multiply(x,x);if((y&1)!=0)res=op.Multiply(res,x);}return res;}[凾(256)]public static long Pow(this long x,long y)=>Pow(x,y);}} namespace Kzrnm.Competitive.Internal{internal enum ArrayMatrixKind{Zero,Identity,Normal,}} namespace Kzrnm.Competitive{using Kd=Internal.ArrayMatrixKind;public readonly struct BitOrMatrix{public bool this[int row,int col]=>Value[row][col];public readonly BitArray[]Value;public static readonly BitOrMatrix Zero=new BitOrMatrix(Kd.Zero);public static readonly BitOrMatrix Identity=new BitOrMatrix(Kd.Identity);public static BitOrMatrix AdditiveIdentity=>Zero;public static BitOrMatrix MultiplicativeIdentity=>Identity;internal readonly Kd kind;internal BitOrMatrix(Kd kind){this.kind=kind;Value=null;}public BitOrMatrix(BitArray[]value){Value=value;kind=Kd.Normal;}public BitOrMatrix(bool[][]value):this(value.Select(a=>new BitArray(a)).ToArray()){}private static BitOrMatrix ThrowNotSupportResponse()=>throw new NotSupportedException();public bool IsZero=>kind is Kd.Zero;private static BitArray[]NormalZeroMatrix(int row,int col){var arr=new BitArray[row];for(int i=0;iy.kind switch{Kd.Zero=>Zero,Kd.Identity=>Identity,_=>new BitOrMatrix(CloneArray(y.Value)),},Kd.Identity=>y.kind switch{Kd.Zero=>Identity,Kd.Identity=>ThrowNotSupportResponse(),_=>y.AddIdentity(),},_=>y.kind switch{Kd.Zero=>new BitOrMatrix(CloneArray(x.Value)),Kd.Identity=>x.AddIdentity(),_=>x.Add(y),},};}[凾(256)]public static BitOrMatrix operator+(BitOrMatrix x)=>x;private BitOrMatrix Multiply(BitOrMatrix other){var val=Value;var otherArr=other.Value;var res=new BitArray[val.Length];for(int i=0;iy.kind switch{Kd.Normal=>new BitOrMatrix(NormalZeroMatrix(y.Value.Length,y.Value[0].Length)),_=>Zero,},Kd.Identity=>y.kind switch{Kd.Zero=>Zero,Kd.Identity=>Identity,_=>y,},_=>y.kind switch{Kd.Zero=>new BitOrMatrix(NormalZeroMatrix(x.Value.Length,x.Value[0].Length)),Kd.Identity=>x,_=>x.Multiply(y),},};}public static BitArray operator*(BitOrMatrix mat,bool[]vector)=>mat.Multiply(new BitArray(vector));public static BitArray operator*(BitOrMatrix mat,BitArray vector)=>mat.Multiply(vector);public BitArray Multiply(BitArray vector){var val=Value;var res=new bool[val.Length];for(int i=0;iobj is BitOrMatrix x&&Equals(x);[凾(256)]public bool Equals(BitOrMatrix other)=>kind==other.kind&&(kind!=Kd.Normal||EqualsMat(Value,other.Value));private static bool EqualsMat(BitArray[]a,BitArray[]b){if(a.Length!=b.Length)return false;var array=new int[(a[0].Length+31)/32];var empty=new int[(a[0].Length+31)/32];for(int i=0;ikind switch{Kd.Normal=>HashCode.Combine(kind,Value.Length,Value[0][0],Value[0][^1],Value[^1][0],Value[^1][^1]),_=>HashCode.Combine(kind),};[凾(256)]public static bool operator==(BitOrMatrix left,BitOrMatrix right)=>left.Equals(right);[凾(256)]public static bool operator!=(BitOrMatrix left,BitOrMatrix right)=>!(left==right);public override string ToString(){if(kind!=Kd.Normal)return kind.ToString();var sb=new StringBuilder(Value.Length*(Value[0].Length+2));foreach(var row in Value){var chr=new char[row.Length];for(int j=0;jrow){row=row.Trim();var b=new BitArray(row.Length);for(int i=0;iMathLibGeneric.Pow(this,y);public struct Operator:IAdditionOperator,IMultiplicationOperator{public BitOrMatrix MultiplyIdentity=>Identity;[凾(256)]public BitOrMatrix Add(BitOrMatrix x,BitOrMatrix y)=>x+y;[凾(256)]public BitOrMatrix Multiply(BitOrMatrix x,BitOrMatrix y)=>x*y;}}} #endregion Expanded by https://github.com/kzrnm/SourceExpander