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 switch
        {
            null => 1,
            var v => v[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>{T Add(T x,T y);}public interface ISubtractOperator<T>{T Subtract(T x,T y);}public interface IMultiplicationOperator<T>{T Multiply(T x,T y);T MultiplyIdentity{get;}}public interface IDivisionOperator<T>:IMultiplicationOperator<T>{T Divide(T x,T y);T Modulo(T x,T y);}public interface IUnaryNumOperator<T>{T Minus(T x);T Increment(T x);T Decrement(T x);}public interface IArithmeticOperator<T>:IAdditionOperator<T>,ISubtractOperator<T>,IMultiplicationOperator<T>,IDivisionOperator<T>,IUnaryNumOperator<T>{}public interface ICompareOperator<T>:IComparer<T>{bool GreaterThan(T x,T y);bool GreaterThanOrEqual(T x,T y);bool LessThan(T x,T y);bool LessThanOrEqual(T x,T y);}public interface IMinMaxValue<T>{T MinValue{get;}T MaxValue{get;}}public interface INumOperator<T>:IArithmeticOperator<T>,ICompareOperator<T>,IMinMaxValue<T>{}public interface IShiftOperator<T>{T LeftShift(T x,int y);T RightShift(T x,int y);}}
namespace AtCoder{public readonly struct LongOperator:INumOperator<long>,IShiftOperator<long>{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)=>x<y;[凾(256)]public bool LessThanOrEqual(long x,long y)=>x<=y;[凾(256)]public int Compare(long x,long y)=>x.CompareTo(y);[凾(256)]public long LeftShift(long x,int y)=>x<<y;[凾(256)]public long RightShift(long x,int y)=>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<buf.Length)buf[buf.Length-1]=10;len+=numberOfBytes;}private void FillNextBuffer(){if((len=input.Read(buf,0,buf.Length))==0){buf[0]=10;len=1;}else if(len<buf.Length)buf[buf.Length-1]=10;pos=0;}[凾(256)]internal byte ReadByte(){if(pos>=len)FillNextBuffer();return buf[pos++];}[凾(256)]public T Read<T>(){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<T>();}static T Throw<T>()=>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>();;byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(' '<b);return encoding.GetString(sb.ToArray());}[凾(256)]public string Ascii(){var sb=new StringBuilder();byte b;do b=ReadByte();while(b<=' ');do{sb.Append((char)b);b=ReadByte();}while(' '<b);return sb.ToString();}[凾(256)]public string Line(){var sb=new List<byte>();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<T>(int count){var arr=new T[count];for(int i=0;i<arr.Length;i++)arr[i]=Read<T>();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 Span<byte>EnsureBuf(int size){if(buf.Length-len<size){Flush();}return buf.AsSpan(len,size);}[凾(256|512)]public _W Write<T>(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{Span<char>s=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(ReadOnlySpan<char>v){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>(T v){Write(v);return Write('\n');}[凾(256)]public _W WriteLine(ReadOnlySpan<char>v){Write(v);return Write('\n');}[凾(256)]public _W WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);[凾(256)]public _W WriteLineJoin<T1,T2>((T1,T2)tuple){Write(tuple.Item1);Write(' ');return WriteLine(tuple.Item2);}[凾(256)]public _W WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');return WriteLine(tuple.Item3);}[凾(256)]public _W WriteLineJoin<T1,T2,T3,T4>((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>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++){if(i!=0)Write(' ');Write(tuple[i]);}return WriteLine();}[凾(256)]public _W WriteLineJoin(params object[]col)=>WriteMany(' ',col);[凾(256)]public _W WriteLineJoin<T1,T2>(T1 v1,T2 v2){Write(v1);Write(' ');return WriteLine(v2);}[凾(256)]public _W WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){Write(v1);Write(' ');Write(v2);Write(' ');return WriteLine(v3);}[凾(256)]public _W WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){Write(v1);Write(' ');Write(v2);Write(' ');Write(v3);Write(' ');return WriteLine(v4);}[凾(256)]public _W WriteLineJoin<T>(params T[]col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);[凾(256)]public _W WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);[凾(256)]public _W WriteLines<T>(T[]col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);[凾(256)]public _W WriteGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}[凾(256)]public _W WriteGrid<TTuple>(IEnumerable<TTuple>tuples)where TTuple:ITuple{foreach(var tup in tuples)WriteLineJoin(tup);return this;}[凾(256)]private _W WriteMany<T>(char sep,IEnumerable<T>col){if(col is T[]array)return WriteMany(sep,(ReadOnlySpan<T>)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<T>(char sep,ReadOnlySpan<T>col){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<T>(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(ReadOnlySpan<char>v)=>cw.WriteLine(v);public static implicit operator O(char[]v)=>cw.WriteLine((ReadOnlySpan<char>)v);public static implicit operator O(string v)=>cw.WriteLine((ReadOnlySpan<char>)v);public static implicit operator O(bool v)=>cw.WriteLine((ReadOnlySpan<char>)(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<int>,IEnumerator<int>{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;i<res.Length;i++){MoveNext();res[i]=Current;}return res;}void IEnumerator.Reset()=>throw new NotSupportedException();void IDisposable.Dispose(){}IEnumerator<int>IEnumerable<int>.GetEnumerator()=>this;IEnumerator IEnumerable.GetEnumerator()=>this;}}}
namespace Kzrnm.Competitive{public static class __ArrayExtension{[凾(256)]public static T[]Fill<T>(this T[]arr,T value){arr.AsSpan().Fill(value);return arr;}[凾(256)]public static T[]Sort<T>(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<T,U>(this T[]arr,Func<T,U>selector)where U:IComparable<U>{Array.Sort(arr.Select(selector).ToArray(),arr);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr,Comparison<T>comparison){Array.Sort(arr,comparison);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr,IComparer<T>comparer){Array.Sort(arr,comparer);return arr;}[凾(256)]public static T[]Reverse<T>(this T[]arr){Array.Reverse(arr);return arr;}[凾(256)]public static ref T Get<T>(this T[]arr,int index){if(index<0)index+=arr.Length;return ref arr[index];}[凾(256)]public static ref readonly T GetOrDummy<T>(this ReadOnlySpan<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this Span<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this T[]arr,int index,T dummy=default)=>ref GetOrDummy(arr.AsSpan(),index,dummy);[凾(256)]public static ref T GetOrDummy<T>(this T[][]arr,int index1,int index2,T dummy=default){if((uint)index1<(uint)arr.Length)return ref GetOrDummy(arr[index1],index2,dummy);Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(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<T>.dummy=dummy;return ref Dummy<T>.dummy;}private static class Dummy<T>{public static T dummy;}[凾(256)]public static int FindByBinarySearch<T,TCv>(this T[]arr,TCv value)where TCv:IComparable<T> =>FindByBinarySearch((ReadOnlySpan<T>)arr,value);[凾(256)]public static int FindByBinarySearch<T,TCv>(this Span<T>arr,TCv value)where TCv:IComparable<T> =>FindByBinarySearch((ReadOnlySpan<T>)arr,value);[凾(256)]public static int FindByBinarySearch<T,TCv>(this ReadOnlySpan<T>arr,TCv value)where TCv:IComparable<T>{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<Dummy>(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<int,ulong>(arr);var l=new List<int>(b.Length);for(var i=0;i<brr.Length;++i)foreach(var bit in brr[i].Bits()){var bb=bit+64*i;if(bb>=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<<rem)&arr[^1]));if((arr.Length&1)!=0){cnt+=BitOperations.PopCount((uint)arr[^1]);arr=arr[..^1];}var brr=MemoryMarshal.Cast<int,ulong>(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<int,ulong>(arr);for(int i=0;i<brr.Length;i++)if(brr[i]!=0)return Math.Min(b.Length,BitOperations.TrailingZeroCount(brr[i])+i*64);if((arr.Length&1)!=0)return Math.Min(b.Length,BitOperations.TrailingZeroCount((uint)arr[^1])+brr.Length*64);return b.Length;}[凾(256)]public static int Msb(this BitArray b){var arr=b.GetArray().AsSpan();var rem=b.Length&31;var m=(uint)arr[^1]&((1u<<rem)-1);if(rem==0)m=(uint)arr[^1];if(m!=0)return BitOperations.Log2(m)+32*(arr.Length-1);arr=arr[..^1];if((arr.Length&1)!=0){m=(uint)arr[^1];if(m!=0)return BitOperations.Log2(m)+32*(arr.Length-1);}var brr=MemoryMarshal.Cast<int,ulong>(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<T>{public T[]arr;}[凾(256)]public static Span<T>AsSpan<T>(this List<T>list,int start=0)=>Unsafe.As<ArrayVal<T>>(list).arr.AsSpan(start,list.Count-start);[凾(256)]public static Span<TTo>Cast<TFrom,TTo>(this Span<TFrom>span)where TFrom:struct where TTo:struct=>MemoryMarshal.Cast<TFrom,TTo>(span);[凾(256)]public static ReadOnlySpan<TTo>Cast<TFrom,TTo>(this ReadOnlySpan<TFrom>span)where TFrom:struct where TTo:struct=>MemoryMarshal.Cast<TFrom,TTo>(span);[凾(256)]public static ref T GetReference<T>(this Span<T>span)=>ref MemoryMarshal.GetReference(span);[凾(256)]public static ref T GetReference<T>(this ReadOnlySpan<T>span)=>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<T>(int len0,T value)where T:struct=>new T[len0].Fill(value);[凾(256)]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;}[凾(256)]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;}[凾(256)]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;}[凾(256)]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;}[凾(256)]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;}[凾(256)]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;}[凾(256)]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;}}}
namespace Kzrnm.Competitive{public static class MathLibGeneric{[凾(256)]public static T Pow<T,TOp>(T x,long y)where TOp:struct,IMultiplicationOperator<T>{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<long,AtCoder.LongOperator>(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;i<arr.Length;i++)arr[i]=new BitArray(col);return arr;}private static BitArray[]CloneArray(BitArray[]arr){var res=new BitArray[arr.Length];for(int i=0;i<arr.Length;i++)res[i]=new BitArray(arr[i]);return res;}private BitOrMatrix AddIdentity(){var arr=CloneArray(Value);for(int i=0;i<arr.Length;i++)arr[i][i]=true;return new BitOrMatrix(arr);}private BitOrMatrix Add(BitOrMatrix other){var otherArr=other.Value;var val=Value;var arr=new BitArray[val.Length];for(int i=0;i<arr.Length;i++)arr[i]=new BitArray(val[i]).Or(otherArr[i]);return new BitOrMatrix(arr);}public static BitOrMatrix operator+(BitOrMatrix x,BitOrMatrix y){return x.kind switch{Kd.Zero=>y.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;i<res.Length;i++){var row=res[i]=new BitArray(otherArr[0].Length);for(int j=0;j<val[i].Length;j++)if(val[i][j])row.Or(otherArr[j]);}return new BitOrMatrix(res);}public static BitOrMatrix operator*(BitOrMatrix x,BitOrMatrix y){return x.kind switch{Kd.Zero=>y.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;i<res.Length;i++)res[i]=new BitArray(val[i]).And(vector).Lsb()<vector.Length;return new BitArray(res);}[凾(256)]public override bool Equals(object obj)=>obj 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;i<a.Length;i++){new BitArray(a[i]).Xor(b[i]).CopyTo(array,0);if(!array.AsSpan().SequenceEqual(empty))return false;}return true;}[凾(256)]public override int GetHashCode()=>kind 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;j<row.Length;j++)chr[j]=row[j]?'1':'0';sb.Append(chr).Append('\n');}return sb.Remove(sb.Length-1,1).ToString();}public static BitOrMatrix Parse(string[]rows){var arr=new BitArray[rows.Length];arr[0]=ParseRow(rows[0].AsSpan().Trim());for(int i=1;i<arr.Length;i++){arr[i]=ParseRow(rows[i].AsSpan().Trim());if(arr[i].Length!=arr[i-1].Length)throw new FormatException("Row length are diffrent.");}return new BitOrMatrix(arr);static BitArray ParseRow(ReadOnlySpan<char>row){row=row.Trim();var b=new BitArray(row.Length);for(int i=0;i<row.Length;i++)b[i]=row[i]!='0';return b;}}public BitOrMatrix Pow(long y)=>MathLibGeneric.Pow<BitOrMatrix,Operator>(this,y);public struct Operator:IAdditionOperator<BitOrMatrix>,IMultiplicationOperator<BitOrMatrix>{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