結果
| 問題 | No.803 Very Limited Xor Subset |
| ユーザー |
 vwxyz
|
| 提出日時 | 2021-09-12 12:21:40 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 26,350 bytes |
| コンパイル時間 | 257 ms |
| コンパイル使用メモリ | 16,000 KB |
| 実行使用メモリ | 23,324 KB |
| 最終ジャッジ日時 | 2024-06-24 00:35:05 |
| 合計ジャッジ時間 | 24,619 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 52 ms
21,788 KB |
| testcase_01 | AC | 52 ms
14,976 KB |
| testcase_02 | AC | 51 ms
14,848 KB |
| testcase_03 | AC | 53 ms
14,848 KB |
| testcase_04 | AC | 54 ms
14,976 KB |
| testcase_05 | AC | 54 ms
14,976 KB |
| testcase_06 | AC | 53 ms
14,848 KB |
| testcase_07 | AC | 51 ms
14,848 KB |
| testcase_08 | AC | 53 ms
14,848 KB |
| testcase_09 | AC | 54 ms
14,848 KB |
| testcase_10 | AC | 54 ms
14,976 KB |
| testcase_11 | AC | 56 ms
14,848 KB |
| testcase_12 | AC | 56 ms
14,848 KB |
| testcase_13 | AC | 52 ms
14,848 KB |
| testcase_14 | AC | 1,973 ms
16,000 KB |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
ソースコード
import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
heap.append(item)
heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
if heap and item < heap[0]:
item, heap[0] = heap[0], item
heapq._siftup_max(heap, 0)
return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
def Extended_Euclid(n,m):
stack=[]
while m:
stack.append((n,m))
n,m=m,n%m
if n>=0:
x,y=1,0
else:
x,y=-1,0
for i in range(len(stack)-1,-1,-1):
n,m=stack[i]
x,y=y,x-(n//m)*y
return x,y
class MOD:
def __init__(self,p,e=1):
self.p=p
self.e=e
self.mod=self.p**self.e
def Pow(self,a,n):
a%=self.mod
if n>=0:
return pow(a,n,self.mod)
else:
assert math.gcd(a,self.mod)==1
x=Extended_Euclid(a,self.mod)[0]
return pow(x,-n,self.mod)
def Build_Fact(self,N):
assert N>=0
self.factorial=[1]
self.cnt=[0]*(N+1)
for i in range(1,N+1):
ii=i
self.cnt[i]=self.cnt[i-1]
while ii%self.p==0:
ii//=self.p
self.cnt[i]+=1
self.factorial.append((self.factorial[-1]*ii)%self.mod)
self.factorial_inve=[None]*(N+1)
self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)
for i in range(N-1,-1,-1):
ii=i+1
while ii%self.p==0:
ii//=self.p
self.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.mod
def Fact(self,N):
return self.factorial[N]*pow(self.p,self.cnt[N],self.mod)%self.mod
def Fact_Inve(self,N):
if self.cnt[N]:
return None
return self.factorial_inve[N]
def Comb(self,N,K,divisible_count=False):
if K<0 or K>N:
return 0
retu=self.factorial[N]*self.factorial_inve[K]*self.factorial_inve[N-K]%self.mod
cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]
if divisible_count:
return retu,cnt
else:
retu*=pow(self.p,cnt,self.mod)
retu%=self.mod
return retu
class Matrix:
def __init__(self,H=0,W=0,matrix=False,eps=1e-12,mod=0,identity=0):
if identity:
if H:
self.H=H
self.W=H
else:
self.H=W
self.W=W
self.matrix=[[0]*self.W for i in range(self.H)]
for i in range(self.H):
self.matrix[i][i]=identity
elif matrix:
self.matrix=matrix
self.H=len(self.matrix)
self.W=len(self.matrix[0]) if self.matrix else 0
else:
self.H=H
self.W=W
self.matrix=[[0]*self.W for i in range(self.H)]
self.mod=mod
self.eps=eps
def __eq__(self,other):
if type(other)!=Matrix:
return False
if self.H!=other.H:
return False
if self.mod:
for i in range(self.H):
for j in range(self.W):
if self.matrix[i][j]%self.mod!=other.matrix[i][j]%self.mod:
return False
else:
for i in range(self.H):
for j in range(self.W):
if abs(self.matrix[i][j]-other.matrix[i][j])>self.eps:
return False
return True
def __ne__(self,other):
if type(other)!=Matrix:
return True
if self.H!=other.H:
return True
if self.mod:
for i in range(self.H):
for j in range(self.W):
if self.matrix[i][j]%self.mod!=other.matrix[i][j]%self.mod:
return True
else:
for i in range(self.H):
for j in range(self.W):
if abs(self.matrix[i][j]-other.matrix[i][j])>self.eps:
return True
return False
def __add__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
if self.mod:
summ=Matrix(matrix=[[(self.matrix[i][j]+other.matrix[i][j])%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
summ=Matrix(matrix=[[self.matrix[i][j]+other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
if self.mod:
summ=Matrix(matrix=[[(self.matrix[i][j]+other)%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
summ=Matrix(matrix=[[self.matrix[i][j]+other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return summ
def __sub__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
if self.mod:
diff=Matrix(matrix=[[(self.matrix[i][j]-other.matrix[i][j])%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
diff=Matrix(matrix=[[self.matrix[i][j]-other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
if self.mod:
diff=Matrix(matrix=[[(self.matrix[i][j]-other)%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
diff=Matrix(matrix=[[self.matrix[i][j]-other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return diff
def __mul__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
if self.mod:
prod=Matrix(matrix=[[(self.matrix[i][j]*other.matrix[i][j])%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
prod=Matrix(matrix=[[self.matrix[i][j]*other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
if self.mod:
prod=Matrix(matrix=[[(self.matrix[i][j]*other)%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
prod=Matrix(matrix=[[self.matrix[i][j]*other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return prod
def __matmul__(self,other):
if type(other)==Matrix:
assert self.W==other.H
prod=Matrix(H=self.H,W=other.W,eps=self.eps,mod=self.mod)
for i in range(self.H):
for j in range(other.W):
for k in range(self.W):
prod.matrix[i][j]+=self.matrix[i][k]*other.matrix[k][j]
if self.mod:
prod.matrix[i][j]%=self.mod
elif type(other)==int:
assert self.H==self.W
if other==0:
prod=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)
elif other==1:
prod=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
prod=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)
doub=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
while other>=2:
if other&1:
prod@=doub
doub@=doub
other>>=1
prod@=doub
return prod
def __truediv__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
if self.mod:
quot=Matrix(matrix=[[(self.matrix[i][j]*MOD(self.mod).Pow(other.matrix[i][j],-1))%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
quot=Matrix(matrix=[[self.matrix[i][j]/other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
if self.mod:
inve=MOD(self.mod).Pow(other,-1)
quot=Matrix(matrix=[[(self.matrix[i][j]*inve)%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
quot=Matrix(matrix=[[self.matrix[i][j]/other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return quot
def __floordiv__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
quot=Matrix(matrix=[[self.matrix[i][j]//other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
quot=Matrix(matrix=[[self.matrix[i][j]//other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return quot
def __mod__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
rema=Matrix(matrix=[[self.matrix[i][j]%other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
rema=Matrix(matrix=[[self.matrix[i][j]%other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return rema
def __pow__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
if self.mod:
powe=Matrix(matrix=[[pow(self.matrix[i][j],other.matrix[i][j],self.mod) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
powe=Matrix(matrix=[[pow(self.matrix[i][j],other.matrix[i][j]) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
if self.mod:
powe=Matrix(matrix=[[pow(self.matrix[i][j],other,self.mod) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
powe=Matrix(matrix=[[pow(self.matrix[i][j],other) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return powe
def __lshift__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
lshi=Matrix(matrix=[[self.matrix[i][j]<<other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
lshi=Matrix(matrix=[[self.matrix[i][j]<<other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return lshi
def __rshift__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
rshi=Matrix(matrix=[[self.matrix[i][j]>>other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
rshi=Matrix(matrix=[[self.matrix[i][j]>>other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return rshi
def __and__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
conj=Matrix(matrix=[[self.matrix[i][j]&other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
conj=Matrix(matrix=[[self.matrix[i][j]&other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return conj
def __or__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
disj=Matrix(matrix=[[self.matrix[i][j]|other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
disj=Matrix(matrix=[[self.matrix[i][j]|other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return disj
def __xor__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
excl=Matrix(matrix=[[self.matrix[i][j]^other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
excl=Matrix(matrix=[[self.matrix[i][j]^other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return excl
def __iadd__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]+=other.matrix[i][j]
if self.mod:
self.matrix[i][j]%=self.mod
else:
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]+=other
if self.mod:
self.matrix[i][j]%=self.mod
return self
def __isub__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]-=other.matrix[i][j]
if self.mod:
self.matrix[i][j]%=self.mod
else:
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]-=other
if self.mod:
self.matrix[i][j]%=self.mod
return self
def __imul__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]*=other.matrix[i][j]
if self.mod:
self.matrix[i][j]%=self.mod
else:
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]*=other
if self.mod:
self.matrix[i][j]%=self.mod
return self
def __imatmul__(self,other):
if type(other)==Matrix:
assert self.W==other.H
prod=Matrix(H=self.H,W=other.W,eps=self.eps,mod=self.mod)
for i in range(self.H):
for j in range(other.W):
for k in range(self.W):
prod.matrix[i][j]+=self.matrix[i][k]*other.matrix[k][j]
if self.mod:
prod.matrix[i][j]%=self.mod
elif type(other)==int:
assert self.H==self.W
if other==0:
return Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)
elif other==1:
prod=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
prod=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)
doub=self
while other>=2:
if other&1:
prod@=doub
doub@=doub
other>>=1
prod@=doub
return prod
def __itruediv__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
if self.mod:
self.matrix[i][j]=self.matrix[i][j]*MOD(self.mod).Pow(other.matrix[i][j],-1)%self.mod
else:
self.matrix[i][j]/=other.matrix[i][j]
else:
if self.mod:
inve=MOD(self.mod).Pow(other,-1)
for i in range(self.H):
for j in range(self.W):
if self.mod:
self.matrix[i][j]=self.matrix[i][j]*inve%self.mod
else:
self.matrix[i][j]/=other
return self
def __ifloordiv__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]//=other.matrix[i][j]
else:
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]//=other
return self
def __imod__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]%=other.matrix[i][j]
else:
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]%=other
return self
def __ipow__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
if self.mod:
self.matrix[i][j]=pow(self.matrix[i][j],other.matrix[i][j],self.mod)
else:
self.matrix[i][j]=pow(self.matrix[i][j],other.matrix[i][j])
else:
for i in range(self.H):
for j in range(self.W):
if self.mod:
self.matrix[i][j]=pow(self.matrix[i][j],other,self.mod)
else:
self.matrix[i][j]=pow(self.matrix[i][j],other)
return self
def __ilshift__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]<<=other.matrix[i][j]
else:
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]<<=other
return self
def __irshift__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]>>=other.matrix[i][j]
else:
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]>>=other
return self
def __iand__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]&=other.matrix[i][j]
else:
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]&=other
return self
def __ior__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]|=other.matrix[i][j]
else:
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]|=other
return self
def __ixor__(self,other):
if type(other)==Matrix:
assert self.H==other.H
assert self.W==other.W
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]^=other.matrix[i][j]
else:
for i in range(self.H):
for j in range(self.W):
self.matrix[i][j]^=other
return self
def __neg__(self):
if self.mod:
nega=Matrix(matrix=[[(-self.matrix[i][j])%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
else:
nega=Matrix(matrix=[[-self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return nega
def __pos__(self):
posi=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return posi
def __invert__(self):
inve=Matrix(matrix=[[~self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return inve
def __abs__(self):
abso=Matrix(matrix=[[abs(self.matrix[i][j]) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
return abso
def __getitem__(self,i):
if type(i)==int:
return self.matrix[i]
elif type(i)==tuple:
i,j=i
if type(i)==int:
i=slice(i,i+1)
if type(j)==int:
j=slice(j,j+1)
return Matrix(matrix=[lst[j] for lst in self.matrix[i]],eps=self.eps,mod=self.mod)
def __contains__(self,x):
for i in range(self.H):
if x in self.matrix[i]:
return True
return False
def __str__(self):
digit=[max(len(str(self.matrix[i][j])) for i in range(self.H)) for j in range(self.W)]
return "\n".join([(" [" if i else "[[")+", ".join([str(self.matrix[i][j]).rjust(digit[j]," ") for j in range(self.W)])+"]" for i in range(self.H)])+"]"
def __bool__(self):
return True
def Transpose(self):
return Matrix(matrix=[[self.matrix[i][j] for i in range(self.H)] for j in range(self.W)])
def Trace(self):
assert self.H==self.W
trace=sum(self.matrix[i][i] for i in range(self.H))
if self.mod:
trace%=self.mod
return trace
def Elem_Raw_Operate_1(self,i1,i2):
self.matrix[i1],self.matrix[i2]=self.matrix[i2],self.matrix[i1]
def Elem_Raw_Operate_2(self,i,c):
if self.mod:
self.matrix[i]=[self.matrix[i][j]*c%self.mod for j in range(self.W)]
else:
self.matrix[i]=[self.matrix[i][j]*c for j in range(self.W)]
def Elem_Raw_Operate_3(self,i1,i2,c):
if self.mod:
self.matrix[i1]=[(self.matrix[i1][j]+c*self.matrix[i2][j])%self.mod for j in range(self.W)]
else:
self.matrix[i1]=[self.matrix[i1][j]+c*self.matrix[i2][j] for j in range(self.W)]
def Elimination(self,determinant=False,inverse_matrix=False,linear_equation=False,rank=False,upper_triangular=False):
h=0
ut=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)
if determinant or inverse_matrix:
assert self.H==self.W
det=1
if inverse_matrix:
assert self.H==self.W
im=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)
if linear_equation:
assert self.H==linear_equation.H
le=Matrix(matrix=[[linear_equation.matrix[i][j] for j in range(linear_equation.W)] for i in range(linear_equation.H)],eps=self.eps,mod=self.mod)
for j in range(ut.W):
for i in range(h,ut.H):
if abs(ut.matrix[i][j])>ut.eps:
if ut.mod:
inve=MOD(ut.mod).Pow(ut.matrix[i][j],-1)
else:
inve=1/ut.matrix[i][j]
ut.Elem_Raw_Operate_1(i,h)
if determinant and h%2!=i%2:
det=(-det)%self.mod
if inverse_matrix:
im.Elem_Raw_Operate_1(i,h)
if linear_equation:
le.Elem_Raw_Operate_1(i,h)
ut.Elem_Raw_Operate_2(h,inve)
if determinant or inverse_matrix:
det*=inve
if ut.mod:
det%=ut.mod
if inverse_matrix:
im.Elem_Raw_Operate_2(h,inve)
if linear_equation:
le.Elem_Raw_Operate_2(h,inve)
for ii in range(ut.H):
if ii==h:
continue
x=-ut.matrix[ii][j]
ut.Elem_Raw_Operate_3(ii,h,x)
if inverse_matrix:
im.Elem_Raw_Operate_3(ii,h,x)
if linear_equation:
le.Elem_Raw_Operate_3(ii,h,x)
h+=1
break
else:
det=0
tpl=()
if determinant:
tpl+=(det,)
if inverse_matrix:
if det<=0:
im=False
tpl+=(im,)
if linear_equation:
tpl+=(le,)
if rank:
tpl+=(h,)
if upper_triangular:
tpl+=(ut,)
if len(tpl)==1:
tpl=tpl[0]
return tpl
N,M,X=map(int,readline().split())
A=list(map(int,readline().split()))
T,L,R=[],[],[]
for _ in range(M):
t,l,r=map(int,readline().split())
l-=1
T.append(t)
L.append(l)
R.append(r)
ans=1
mod=10**9+7
Mat=Matrix(30+M,N,mod=2)
A_Mat=Matrix(30+M,1,mod=2)
for bit in range(30):
for j in range(N):
if A[j]>>bit&1:
Mat[bit][j]=1
if X>>bit&1:
A_Mat[bit][0]=1
for i in range(M):
for j in range(L[i],R[i]):
Mat[30+i][j]=1
A_Mat[30+i][0]=T[i]
A_Mat,rank,Mat=Mat.Elimination(linear_equation=A_Mat,rank=True,upper_triangular=True)
for i in range(rank,30+M):
if A_Mat[i][0]:
ans=0
break
else:
ans=pow(2,N-rank,mod)
print(ans)