using AtCoder.Internal;
using AtCoder.Operators;
using BitArray = System.Collections.BitArray;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using ModInt = AtCoder.StaticModInt<AtCoder.Mod1000000007>;
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 凾 = 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;
        int X = cr;
        int[] A = cr.Repeat(N);
        var bits = new List<BitArray>();
        for (int b = 0; b < 31; b++)
        {
            var bb = new BitArray(N);
            for (int i = 0; i < A.Length; i++)
                bb[i] = A[i].On(b);
            bits.Add(bb);
        }
        var xb = Enumerable.Repeat(false, 31).ToList();
        foreach (var b in X.Bits()) xb[b] = true;
        while (--M >= 0)
        {
            xb.Add(cr.Int != 0);
            int l = cr.Int0;
            int r = cr.Int;
            var bb = new bool[N];
            bb.AsSpan()[l..r].Fill(true);
            bits.Add(new BitArray(bb));
        }
        var len = new BitMatrix(bits.ToArray()).LinearSystem(xb.ToArray()).Length - 1;
        return ModInt.Raw(2).Pow(len).Value;
    }
}
#region Expanded by https://github.com/kzrnm/SourceExpander
//LICENSE:
//https://github.com/kzrnm/Kzrnm.Competitive/blob/master/LICENSE
//https://github.com/kzrnm/Kzrnm.Competitive/blob/master/3rd-party%20Licenses.txt
#pragma warning disable
namespace AtCoder.Internal{public class Barrett{public readonly uint Mod;internal readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1;}[凾(256)]public uint Mul(uint a,uint b){var z=(ulong)a*b;if(Bmi2.X64.IsSupported){var x=Bmi2.X64.MultiplyNoFlags(z,IM);var v=unchecked((uint)(z-x*Mod));if(Mod<=v)v+=Mod;return v;}return(uint)(z%Mod);}}}
namespace AtCoder.Internal{public static class InternalMath{private static readonly Dictionary<uint,int>primitiveRootsCache=new Dictionary<uint,int>(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};[凾(256)]public static int PrimitiveRoot<TMod>()where TMod:struct,IStaticMod{uint m=default(TMod).Mod;if(primitiveRootsCache.TryGetValue(m,out var p)){return p;}return primitiveRootsCache[m]=PrimitiveRootCalculate<TMod>();}static int PrimitiveRootCalculate<TMod>()where TMod:struct,IStaticMod{int m=(int)default(TMod).Mod;Span<int>divs=stackalloc int[20];divs[0]=2;int cnt=1;int x=(m-1)/2;while(x%2==0){x>>=1;}for(int i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;while(x%i==0){x/=i;}}}if(x>1){divs[cnt++]=x;}divs=divs.Slice(0,cnt);for(int g=2;;g++){foreach(var d in divs)if(new StaticModInt<TMod>(g).Pow((m-1)/d).Value==1)goto NEXT;return g;NEXT:{}}}[凾(256)]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;}}[凾(256)]public static long SafeMod(long x,long m){x%=m;if(x<0)x+=m;return x;}[凾(256)]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<byte>bases=stackalloc byte[3]{2,7,61};foreach(long a in bases){long t=d;long y=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;}[凾(256)]private 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)SafeMod(x,m);while(0<n){if((n&1)!=0)r=barrett.Mul(r,y);y=barrett.Mul(y,y);n>>=1;}return r;}[凾(256)]public static ulong FloorSumUnsigned(ulong n,ulong m,ulong a,ulong b){ulong ans=0;while(true){if(a>=m){ans+=(n-1)*n/2*(a/m);a%=m;}if(b>=m){ans+=n*(b/m);b%=m;}ulong yMax=a*n+b;if(yMax<m)return ans;(n,m,a,b)=(yMax/m,a,m,yMax%m);}}}}
namespace AtCoder{public 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 StaticModInt<T>:IEquatable<StaticModInt<T>>,IFormattable 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;public static StaticModInt<T>Zero=>default;public static StaticModInt<T>One=>new StaticModInt<T>(1u);[凾(256)]public static StaticModInt<T>Raw(int v){var u=unchecked((uint)v);return new StaticModInt<T>(u);}[凾(256)]public StaticModInt(long v):this(Round(v)){}[凾(256)]public StaticModInt(ulong v):this((uint)(v%op.Mod)){}[凾(256)]private StaticModInt(uint v)=>_v=v;[凾(256)]private static uint Round(long v){var x=v%op.Mod;if(x<0){x+=op.Mod;}return(uint)x;}[凾(256)]public static StaticModInt<T>operator ++(StaticModInt<T>v){var x=v._v+1;if(x==op.Mod){x=0;}return new StaticModInt<T>(x);}[凾(256)]public static StaticModInt<T>operator --(StaticModInt<T>v){var x=v._v;if(x==0){x=op.Mod;}return new StaticModInt<T>(x-1);}[凾(256)]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);}[凾(256)]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);}}[凾(256)]public static StaticModInt<T>operator*(StaticModInt<T>lhs,StaticModInt<T>rhs)=>new StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));[凾(256)]public static StaticModInt<T>operator/(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs*rhs.Inv();[凾(256)]public static StaticModInt<T>operator+(StaticModInt<T>v)=>v;[凾(256)]public static StaticModInt<T>operator-(StaticModInt<T>v)=>new StaticModInt<T>(v._v==0?0:op.Mod-v._v);[凾(256)]public static bool operator==(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v==rhs._v;[凾(256)]public static bool operator!=(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v!=rhs._v;[凾(256)]public static implicit operator StaticModInt<T>(int v)=>new StaticModInt<T>(v);[凾(256)]public static implicit operator StaticModInt<T>(uint v)=>new StaticModInt<T>((long)v);[凾(256)]public static implicit operator StaticModInt<T>(long v)=>new StaticModInt<T>(v);[凾(256)]public static implicit operator StaticModInt<T>(ulong v)=>new StaticModInt<T>(v);[凾(256)]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;}[凾(256)]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 string ToString(string format,IFormatProvider formatProvider)=>_v.ToString(format,formatProvider);public override bool Equals(object obj)=>obj is StaticModInt<T>m&&Equals(m);[凾(256)]public bool Equals(StaticModInt<T>other)=>_v==other._v;public override int GetHashCode()=>_v.GetHashCode();}}
namespace AtCoder.Operators{public interface IAdditionOperator<T>{T Add(T x,T y);}public interface ISubtractOperator<T>{T Subtract(T x,T y);}public interface IMultiplicationOperator<T>{T Multiply(T x,T y);T MultiplyIdentity{get;}}public interface IDivisionOperator<T>:IMultiplicationOperator<T>{T Divide(T x,T y);T Modulo(T x,T y);}public interface IUnaryNumOperator<T>{T Minus(T x);T Increment(T x);T Decrement(T x);}public interface IArithmeticOperator<T>:IAdditionOperator<T>,ISubtractOperator<T>,IMultiplicationOperator<T>,IDivisionOperator<T>,IUnaryNumOperator<T>{}public interface ICompareOperator<T>:IComparer<T>{bool GreaterThan(T x,T y);bool GreaterThanOrEqual(T x,T y);bool LessThan(T x,T y);bool LessThanOrEqual(T x,T y);}public interface IMinMaxValue<T>{T MinValue{get;}T MaxValue{get;}}public interface INumOperator<T>:IArithmeticOperator<T>,ICompareOperator<T>,IMinMaxValue<T>{}public interface IShiftOperator<T>{T LeftShift(T x,int y);T RightShift(T x,int y);}}
namespace 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 class RepeatReader<R>where R:ConsoleReader{internal readonly R cr;internal readonly int count;[凾(256)]public RepeatReader(R cr,int count){this.cr=cr;this.count=count;}[凾(256)]public string[]Ascii()=>Read<string>();[凾(256)]public int[]Int()=>Read<int>();[凾(256)]public uint[]UInt()=>Read<uint>();[凾(256)]public long[]Long()=>Read<long>();[凾(256)]public ulong[]ULong()=>Read<ulong>();[凾(256)]public double[]Double()=>Read<double>();[凾(256)]public decimal[]Decimal()=>Read<decimal>();[凾(256)]public string[]Line(){var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.Line();return arr;}[凾(256)]public string[]String(){var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.String();return arr;}[凾(256)]public int[]Int0(){var arr=new int[count];for(var i=0;i<count;i++)arr[i]=cr.Int0();return arr;}[凾(256)]public uint[]UInt0(){var arr=new uint[count];for(var i=0;i<count;i++)arr[i]=cr.UInt0();return arr;}[凾(256)]public long[]Long0(){var arr=new long[count];for(var i=0;i<count;i++)arr[i]=cr.Long0();return arr;}[凾(256)]public ulong[]ULong0(){var arr=new ulong[count];for(var i=0;i<count;i++)arr[i]=cr.ULong0();return arr;}[凾(256)]public static implicit operator string[](RepeatReader<R>rr)=>rr.Read<string>();[凾(256)]public static implicit operator int[](RepeatReader<R>rr)=>rr.Read<int>();[凾(256)]public static implicit operator uint[](RepeatReader<R>rr)=>rr.Read<uint>();[凾(256)]public static implicit operator long[](RepeatReader<R>rr)=>rr.Read<long>();[凾(256)]public static implicit operator ulong[](RepeatReader<R>rr)=>rr.Read<ulong>();[凾(256)]public static implicit operator double[](RepeatReader<R>rr)=>rr.Double();[凾(256)]public static implicit operator decimal[](RepeatReader<R>rr)=>rr.Decimal();public T[]Read<T>(){var arr=new T[count];for(int i=0;i<arr.Length;i++)arr[i]=cr.Read<T>();return arr;}[凾(256)]public T[]Select<T>(Func<R,T>factory){var c=count;var arr=new T[c];for(var i=0;i<c;i++)arr[i]=factory(cr);return arr;}[凾(256)]public T[]Select<T>(Func<R,int,T>factory){var c=count;var arr=new T[c];for(var i=0;i<c;i++)arr[i]=factory(cr,i);return arr;}}public static class RepeatEx{[凾(256)]public static RepeatReader<ConsoleReader>Repeat(this ConsoleReader cr,int count)=>new RepeatReader<ConsoleReader>(cr,count);}}
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{public class PropertyRepeatReader:RepeatReader<PropertyConsoleReader>{public PropertyRepeatReader(PropertyConsoleReader cr,int count):base(cr,count){}public new string[]Ascii=>Ascii();public new int[]Int=>Int();public new uint[]UInt=>UInt();public new long[]Long=>Long();public new ulong[]ULong=>ULong();public new double[]Double=>Double();public new decimal[]Decimal=>Decimal();public new string[]Line=>Line();public new string[]String=>String();public new int[]Int0=>Int0();public new uint[]UInt0=>UInt0();public new long[]Long0=>Long0();public new ulong[]ULong0=>ULong0();}public static class PRepeatEx{[凾(256)]public static PropertyRepeatReader Repeat(this PropertyConsoleReader cr,int count)=>new PropertyRepeatReader(cr,count);}}
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 __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 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{public enum ArrayMatrixKind{Zero,Identity,Normal,}}
namespace Kzrnm.Competitive{using Kd=Internal.ArrayMatrixKind;public readonly struct BitMatrix{public bool this[int row,int col]=>Value[row][col];public readonly BitArray[]Value;public static readonly BitMatrix Zero=new BitMatrix(Kd.Zero);public static readonly BitMatrix Identity=new BitMatrix(Kd.Identity);public static BitMatrix AdditiveIdentity=>Zero;public static BitMatrix MultiplicativeIdentity=>Identity;internal readonly Kd kind;internal BitMatrix(Kd kind){this.kind=kind;Value=null;}public BitMatrix(BitArray[]value){Value=value;kind=Kd.Normal;}public BitMatrix(bool[][]value):this(value.Select(a=>new BitArray(a)).ToArray()){}private static BitMatrix 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 BitMatrix AddIdentity(){var arr=CloneArray(Value);for(int i=0;i<arr.Length;i++)arr[i][i]=!arr[i][i];return new BitMatrix(arr);}private BitMatrix Add(BitMatrix 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]).Xor(otherArr[i]);return new BitMatrix(arr);}public static BitMatrix operator+(BitMatrix x,BitMatrix y){return x.kind switch{Kd.Zero=>y.kind switch{Kd.Zero=>Zero,Kd.Identity=>Identity,_=>new BitMatrix(CloneArray(y.Value)),},Kd.Identity=>y.kind switch{Kd.Zero=>Identity,Kd.Identity=>ThrowNotSupportResponse(),_=>y.AddIdentity(),},_=>y.kind switch{Kd.Zero=>new BitMatrix(CloneArray(x.Value)),Kd.Identity=>x.AddIdentity(),_=>x.Add(y),},};}[凾(256)]public static BitMatrix operator+(BitMatrix x)=>x;public static BitMatrix operator-(BitMatrix x){var val=x.Value;var arr=new BitArray[val.Length];for(int i=0;i<arr.Length;i++)arr[i]=new BitArray(val[i]).Not();return new BitMatrix(arr);}public static BitMatrix operator~(BitMatrix x)=>-x;public static BitMatrix operator-(BitMatrix x,BitMatrix y)=>x+y;public static BitMatrix operator^(BitMatrix x,BitMatrix y)=>x+y;private BitMatrix Multiply(BitMatrix 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.Xor(otherArr[j]);}return new BitMatrix(res);}public static BitMatrix operator*(BitMatrix x,BitMatrix y){return x.kind switch{Kd.Zero=>y.kind switch{Kd.Normal=>new BitMatrix(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 BitMatrix(NormalZeroMatrix(x.Value.Length,x.Value[0].Length)),Kd.Identity=>x,_=>x.Multiply(y),},};}public static BitArray operator*(BitMatrix mat,bool[]vector)=>mat.Multiply(new BitArray(vector));public static BitArray operator*(BitMatrix 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).PopCount()&1)!=0;return new BitArray(res);}public BitMatrix Inv(){var orig=Value;var arr=new BitArray[orig.Length];for(int i=0;i<arr.Length;i++){var row=arr[i]=new BitArray(orig[i]);row.Length*=2;row[arr.Length+i]=true;}GaussianEliminationImpl(arr,true);var ix=arr.Length-1;if(!arr[ix][ix])return Zero;var res=new BitArray[arr.Length];for(int i=0;i<res.Length;i++){res[i]=new BitArray(res.Length);for(int j=0;j<res.Length;j++){res[i][j]=arr[i][res.Length+j];}}return new BitMatrix(res);}public BitMatrix GaussianElimination(bool isReduced=true){var arr=CloneArray(Value);GaussianEliminationImpl(arr,isReduced);return new BitMatrix(arr);}private static List<int>GaussianEliminationImpl(BitArray[]arr,bool isReduced){var idx=new List<int>(arr.Length);int r=0;int width=arr[0].Length;for(int x=0;x<width&&r<arr.Length;x++){if(!SearchNonZero(arr,r,x))continue;var arrR=arr[r];for(int y=isReduced?0:r+1;y<arr.Length;y++){var arrY=arr[y];if(y==r||!arrY[x])continue;arrY.Xor(arrR);} ++r;idx.Add(x);}return idx;}private static bool SearchNonZero(BitArray[]mat,int r,int x){for(int y=r;y<mat.Length;y++)if(mat[y][x]){(mat[r],mat[y])=(mat[y],mat[r]);return true;}return false;}public BitArray[]LinearSystem(bool[]vector){var impl=Value.Zip(vector,(row,v)=>{row=new BitArray(row);++row.Length;row[^1]=v;return row;}).ToArray();var idxs=GaussianEliminationImpl(impl,false).AsSpan();var r=idxs.Length;int w=Value[0].Length;if(idxs[^1]==w)return null;for(int i=r;i<impl.Length;i++){if(impl[i][^1])return null;}var used=new HashSet<int>(Enumerable.Range(0,w));var lst=new List<BitArray>(w);{var v=new BitArray(w);for(int y=idxs.Length-1;y>=0;y--){int f=idxs[y];used.Remove(f);v[f]=impl[y][^1];for(int x=f+1;x<w;x++)v[f]^=v[x]&&impl[y][x];}lst.Add(v);}foreach(var s in used){var v=new BitArray(w);v[s]=true;for(int y=idxs.Length-1;y>=0;y--){int f=idxs[y];for(int x=f+1;x<w;x++)v[f]^=v[x]&&impl[y][x];}lst.Add(v);}return lst.ToArray();}[凾(256)]public override bool Equals(object obj)=>obj is BitMatrix x&&Equals(x);[凾(256)]public bool Equals(BitMatrix 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==(BitMatrix left,BitMatrix right)=>left.Equals(right);[凾(256)]public static bool operator!=(BitMatrix left,BitMatrix 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 BitMatrix 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 BitMatrix(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 BitMatrix Pow(long y)=>MathLibGeneric.Pow<BitMatrix,Operator>(this,y);public struct Operator:IArithmeticOperator<BitMatrix>{public BitMatrix MultiplyIdentity=>Identity;[凾(256)]public BitMatrix Add(BitMatrix x,BitMatrix y)=>x+y;[凾(256)]public BitMatrix Subtract(BitMatrix x,BitMatrix y)=>x-y;[凾(256)]public BitMatrix Multiply(BitMatrix x,BitMatrix y)=>x*y;[凾(256)]public BitMatrix Minus(BitMatrix x)=>-x;[凾(256)]public BitMatrix Increment(BitMatrix x)=>throw new NotSupportedException();[凾(256)]public BitMatrix Decrement(BitMatrix x)=>throw new NotSupportedException();[凾(256)]public BitMatrix Divide(BitMatrix x,BitMatrix y)=>throw new NotSupportedException();[凾(256)]public BitMatrix Modulo(BitMatrix x,BitMatrix y)=>throw new NotSupportedException();}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander