pub use __cargo_equip::prelude::*;

use bit_matrix::BitMatrix;
use proconio::{fastout, input, marker::Usize1};
use static_modint::ModInt1000000007 as MInt;

#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
        x: u32,
        a: [u32; n],
        t_l_r: [(u8, Usize1, Usize1); m],
    }
    let (mat, b) = {
        let mut mat = BitMatrix::new(32 + m, n);
        for (i, a) in a.into_iter().enumerate() {
            for bit in 0..32 {
                if ((a >> bit) & 1) > 0 {
                    mat.set(bit, i, true);
                }
            }
        }
        let mut b = vec![false; 32 + m];
        for bit in 0..32 {
            if ((x >> bit) & 1) > 0 {
                b[bit] = true;
            }
        }
        for (i, (t, l, r)) in t_l_r.into_iter().enumerate() {
            let i = i + 32;
            b[i] = t == 1;
            for j in l..=r {
                mat.set(i, j, true);
            }
        }
        (mat, b)
    };
    let ans = if let Some((free_dom, _)) = mat.linear_equation(&b) {
        MInt::new(2).pow(free_dom as u64)
    } else {
        MInt::new(0)
    };
    println!("{}", ans);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `bit_matrix 0.1.0 (path+████████████████████████████████████████████████████████████)`                          published in ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::bit_matrix`
///  - `bitset 0.1.0 (path+███████████████████████████████████████████████████)`                                       published in ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__bitset_0_1_0`
///  - `internal_type_traits 0.1.0 (path+███████████████████████████████████████████████████████████████████████████)` published in **missing**                                           licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_type_traits_0_1_0`
///  - `modint_traits 0.1.0 (path+████████████████████████████████████████████████████████████████████)`               published in **missing**                                           licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__modint_traits_0_1_0`
///  - `static_modint 0.1.0 (path+█████████████████████████████████████████████████████████████████)`                  published in ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::static_modint`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod bit_matrix {use crate::__cargo_equip::preludes::bit_matrix::*;use bitset::BitSet;use std::ops::{Add,AddAssign,Index,Mul,MulAssign};#[derive(Debug,Clone,PartialEq,Eq)]pub struct BitMatrix{height:usize,width:usize,data:Vec<BitSet>,}impl From<Vec<Vec<bool>>>for BitMatrix{fn from(v:Vec<Vec<bool>>)->Self{let height=v.len();let width=v[0].len();let data=v.into_iter().map(BitSet::from).collect();Self{height,width,data,}}}impl<const H:usize,const W:usize>From<[[bool;W];H]>for BitMatrix{fn from(v:[[bool;W];H])->Self{let height=H;let width=W;let data=v.into_iter().map(BitSet::from).collect();Self{height,width,data,}}}impl From<Vec<BitSet>>for BitMatrix{fn from(v:Vec<BitSet>)->Self{let height=v.len();let width=v[0].size();Self{height,width,data:v,}}}impl<const H:usize>From<[BitSet;H]>for BitMatrix{fn from(v:[BitSet;H])->Self{let height=H;let width=v[0].size();Self{height,width,data:v.to_vec(),}}}impl BitMatrix{pub fn new(height:usize,width:usize)->Self{Self{height,width,data:vec![BitSet::new(width);height],}}pub fn get(&self,row:usize,col:usize)->bool{assert!(row<self.height&&col<self.width);self.data[row][col]}pub fn set(&mut self,row:usize,col:usize,b:bool){assert!(row<self.height&&col<self.width);self.data[row].set(col,b);}pub fn gauss_jordan(&mut self,is_extended:bool)->usize{let mut rank=0;let col_end=if is_extended{self.width-1}else{self.width};for col in 0..col_end{let mut pivot=None;for row in rank..self.height{if self.data[row][col]{pivot=Some(row);break;}}if let Some(pivot)=pivot{self.data.swap(rank,pivot);for row in 0..self.height{if row!=rank&&self.data[row][col]{unsafe{*self.data.as_mut_ptr().add(row)^=&self.data[rank];}}}rank+=1;}}rank}pub fn linear_equation(&self,b:&[bool])->Option<(usize,Vec<bool>)>{assert_eq!(self.height,b.len());let mut mat=BitMatrix::new(self.height,self.width+1);#[allow(clippy::needless_range_loop)]for i in 0..self.height{for j in 0..self.width{mat.set(i,j,self.get(i,j));}mat.set(i,self.width,b[i]);}let rank=mat.gauss_jordan(true);for i in rank..self.height{if mat.get(i,self.width){return None;}}let mut ans=vec![false;self.width];let mut cur_col=0;for r in 0..rank{while cur_col<self.width&&!mat.get(r,cur_col){cur_col+=1;}assert!(cur_col<self.width);ans[cur_col]=mat.get(r,self.width);cur_col+=1;}let freedom=self.width-rank;Some((freedom,ans))}pub fn unit(n:usize)->Self{let mut res=Self::new(n,n);for i in 0..n{res.set(i,i,true);}res}pub fn transpose(&self)->Self{let mut res=Self::new(self.width,self.height);for i in 0..self.height{for j in 0..self.width{res.set(j,i,self.get(i,j));}}res}pub fn pow(&self,mut n:u64)->Self{assert_eq!(self.height,self.width);let mut res=Self::unit(self.height);let mut a=self.clone();while n>0{if(n&1)==1{res*=&a;}a=&a*&a;n>>=1;}res}}impl Index<usize>for BitMatrix{type Output=BitSet;fn index(&self,index:usize)->&Self::Output{&self.data[index]}}impl AddAssign<&Self>for BitMatrix{fn add_assign(&mut self,rhs:&Self){assert_eq!(self.height,rhs.height);assert_eq!(self.width,rhs.width);for(l,r)in self.data.iter_mut().zip(&rhs.data){*l^=r;}}}impl Add<&Self>for BitMatrix{type Output=Self;fn add(mut self,rhs:&Self)->Self{self+=rhs;self}}impl Mul<&BitMatrix>for&BitMatrix{type Output=BitMatrix;fn mul(self,rhs:&BitMatrix)->BitMatrix{assert_eq!(self.width,rhs.height);let mut ret=BitMatrix::new(self.height,rhs.width);let rhs=rhs.transpose();for i in 0..self.height{for j in 0..rhs.height{ret.set(i,j,self.data[i].dot(&rhs.data[j]));}}ret}}impl Mul<&Self>for BitMatrix{type Output=Self;fn mul(self,rhs:&Self)->Self{&self*rhs}}impl MulAssign<&Self>for BitMatrix{fn mul_assign(&mut self,rhs:&Self){*self=&*self*rhs;}}}
        pub mod __bitset_0_1_0 {use std::ops::{BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Index,Not,Shl,ShlAssign,Shr,ShrAssign,};#[derive(Debug,Clone,PartialEq,Eq,Hash)]pub struct BitSet{buf:Vec<u64>,size:usize,}macro_rules!out_of_bounds{($size:expr,$i:expr)=>{assert!($i<$size,"index out of bounds: the len is {} but the index is {}",$size,$i);};}impl From<Vec<bool>>for BitSet{fn from(v:Vec<bool>)->Self{let size=v.len();let mut buf=vec![0;(size+63)/64];for i in 0..size{if v[i]{buf[i>>6]|=1<<(i&63);}}Self{buf,size}}}impl<const N:usize>From<[bool;N]>for BitSet{fn from(v:[bool;N])->Self{let size=N;let mut buf=vec![0;(size+63)/64];for i in 0..size{if v[i]{buf[i>>6]|=1<<(i&63);}}Self{buf,size}}}impl BitSet{pub fn new(size:usize)->Self{let len=(size+63)/64;Self{buf:vec![0;len],size,}}#[inline]pub fn size(&self)->usize{self.size}#[inline]pub fn get(&self,i:usize)->bool{out_of_bounds!(self.size,i);let x=self.buf[i>>6];let mask=1<<(i&63);(x&mask)!=0}#[inline]pub fn set(&mut self,i:usize,b:bool){out_of_bounds!(self.size,i);if b{self.buf[i>>6]|=1<<(i&63);}else{self.buf[i>>6]&=!(1<<(i&63));}}#[inline]pub fn flip(&mut self,i:usize){out_of_bounds!(self.size,i);self.buf[i>>6]^=1<<(i&63);}#[inline]pub fn count_ones(&self)->u32{self.buf.iter().map(|&x|x.count_ones()).sum()}#[inline]pub fn count_zeros(&self)->u32{self.size as u32-self.count_ones()}#[inline]pub fn none(&self)->bool{self.count_ones()==0}#[inline]pub fn all(&self)->bool{self.count_ones()==self.size as u32}#[inline]pub fn any(&self)->bool{self.count_ones()>0}#[inline]pub fn chomp(&mut self){let r=self.size&63;if r>0{if let Some(last)=self.buf.last_mut(){let d=64-r;*last=(*last<<d)>>d;}}}pub fn dot(&self,other:&Self)->bool{assert_eq!(self.size,other.size);self.buf.iter().zip(&other.buf).map(|(a,b)|((a&b).count_ones()&1)==1).fold(false,|acc,x|acc^x)}}impl Index<usize>for BitSet{type Output=bool;#[inline]fn index(&self,i:usize)->&bool{out_of_bounds!(self.size,i);let x=self.buf[i>>6];let mask=1<<(i&63);if(x&mask)==0{&false}else{&true}}}impl<'a>BitXorAssign<&'a BitSet>for BitSet{#[inline]fn bitxor_assign(&mut self,rhs:&'a BitSet){for(a,b)in self.buf.iter_mut().zip(&rhs.buf){*a^=*b;}self.chomp();}}impl<'a>BitAndAssign<&'a BitSet>for BitSet{#[inline]fn bitand_assign(&mut self,rhs:&'a BitSet){for(a,b)in self.buf.iter_mut().zip(&rhs.buf){*a&=*b;}}}impl<'a>BitOrAssign<&'a BitSet>for BitSet{#[inline]fn bitor_assign(&mut self,rhs:&'a BitSet){for(a,b)in self.buf.iter_mut().zip(&rhs.buf){*a|=*b;}self.chomp();}}macro_rules!impl_bit_op{($op:ident,$op_assign:ident,$f:ident)=>{impl<'a>$op<&'a BitSet>for BitSet{type Output=BitSet;#[inline]fn$f(mut self,rhs:&'a BitSet)->Self::Output{self.$op_assign(rhs);self}}impl<'a,'b>$op<&'b BitSet>for&'a BitSet{type Output=BitSet;#[inline]fn$f(self,rhs:&'b BitSet)->Self::Output{let mut res=self.clone();res.$op_assign(rhs);res}}};}impl_bit_op!(BitXor,bitxor_assign,bitxor);impl_bit_op!(BitAnd,bitand_assign,bitand);impl_bit_op!(BitOr,bitor_assign,bitor);impl Not for BitSet{type Output=Self;#[inline]fn not(mut self)->Self{for x in&mut self.buf{*x=!*x;}self.chomp();self}}impl<'a>Not for&'a BitSet{type Output=BitSet;#[inline]fn not(self)->Self::Output{!self.clone()}}impl ShlAssign<usize>for BitSet{#[inline]fn shl_assign(&mut self,rhs:usize){let q=rhs>>6;let r=rhs&63;if q>=self.buf.len(){for x in&mut self.buf{*x=0;}return;}if r==0{for i in(q..self.buf.len()).rev(){*unsafe{self.buf.get_unchecked_mut(i)}=*unsafe{self.buf.get_unchecked(i-q)};}}else{for i in(q+1..self.buf.len()).rev(){*unsafe{self.buf.get_unchecked_mut(i)}=(unsafe{self.buf.get_unchecked(i-q)}<<r)|(unsafe{self.buf.get_unchecked(i-q-1)}>>(64-r));}*unsafe{self.buf.get_unchecked_mut(q)}=unsafe{self.buf.get_unchecked(0)}<<r;}for x in&mut self.buf[..q]{*x=0;}self.chomp();}}impl ShrAssign<usize>for BitSet{#[inline]fn shr_assign(&mut self,rhs:usize){let q=rhs>>6;let r=rhs&63;if q>=self.buf.len(){for x in&mut self.buf{*x=0;}return;}if r==0{for i in 0..self.buf.len()-q{*unsafe{self.buf.get_unchecked_mut(i)}=*unsafe{self.buf.get_unchecked(i+q)};}}else{for i in 0..self.buf.len()-q-1{*unsafe{self.buf.get_unchecked_mut(i)}=(unsafe{self.buf.get_unchecked(i+q)}>>r)|(unsafe{self.buf.get_unchecked(i+q+1)}<<(64-r));}let len=self.buf.len();*unsafe{self.buf.get_unchecked_mut(len-q-1)}=unsafe{self.buf.get_unchecked(len-1)}>>r;}let len=self.buf.len();for x in&mut self.buf[len-q..]{*x=0;}}}macro_rules!impl_shift_op{($op:ident,$op_assign:ident,$f:ident)=>{impl$op<usize>for BitSet{type Output=BitSet;#[inline]fn$f(mut self,rhs:usize)->Self::Output{self.$op_assign(rhs);self}}impl<'a>$op<usize>for&'a BitSet{type Output=BitSet;#[inline]fn$f(self,rhs:usize)->Self::Output{let mut res=self.clone();res.$op_assign(rhs);res}}};}impl_shift_op!(Shl,shl_assign,shl);impl_shift_op!(Shr,shr_assign,shr);}
        pub mod __internal_type_traits_0_1_0 {use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Sub,SubAssign};pub trait Integral:Copy+Add<Output=Self>+AddAssign+Sub<Output=Self>+SubAssign+Ord+Zero+One+BoundedBelow+BoundedAbove+Display+Debug{}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}}impl Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}
        pub mod __modint_traits_0_1_0 {use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use std::str::FromStr;pub trait ModInt:Debug+Default+Clone+PartialEq+Eq+Display+Copy+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign+Neg<Output=Self>+FromStr{fn new<T:RemEuclidU32>(x:T)->Self;fn raw(x:u32)->Self;fn value(&self)->u32;fn modulus()->u32;fn pow(&self,mut n:u64)->Self{let mut ret=Self::new(1);let mut base=*self;while n>0{if n&1==1{ret*=base;}base*=base;n>>=1;}ret}#[inline]fn inv(&self)->Self{let(g,x)=inv_gcd(self.value(),Self::modulus());assert_eq!(g,1);Self::raw(x)}}fn inv_gcd(a:u32,b:u32)->(u32,u32){assert!(a<b);if a==0{return(b,0);}let mut s=b;let mut t=a;let mut m0=0_i32;let mut m1=1_i32;while t!=0{let u=s/t;s-=t*u;m0-=m1*(u as i32);std::mem::swap(&mut s,&mut t);std::mem::swap(&mut m0,&mut m1);}if m0<0{m0+=(b/s)as i32;}(s,m0 as u32)}pub trait RemEuclidU32:Copy{fn rem_euclid_u32(self,modulus:u32)->u32;}impl RemEuclidU32 for u8{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}}impl RemEuclidU32 for u16{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}}impl RemEuclidU32 for u32{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self%modulus}}impl RemEuclidU32 for u64{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%modulus as u64)as u32}}impl RemEuclidU32 for usize{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{let casted:u64=self.try_into().unwrap();casted.rem_euclid_u32(modulus)}}impl RemEuclidU32 for u128{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%modulus as u128)as u32}}#[inline]fn neg(val:u32,modulus:u32)->u32{if val==0{0}else{modulus-val}}macro_rules!impl_rem_euclid_u32_for_signed{($($t:ty),*)=>{$(impl RemEuclidU32 for$t{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{if self<0{neg(self.unsigned_abs().rem_euclid_u32(modulus),modulus)}else{self.unsigned_abs().rem_euclid_u32(modulus)}}})*};}impl_rem_euclid_u32_for_signed!(i8,i16,i32,i64,isize,i128);macro_rules!impl_rem_for_borrow{($($t:ty),*)=>{$(impl RemEuclidU32 for&$t{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(*self).rem_euclid_u32(modulus)}})*};}impl_rem_for_borrow!(u8,u16,u32,u64,usize,u128,i8,i16,i32,i64,isize,i128);}
        pub mod static_modint {use crate::__cargo_equip::preludes::static_modint::*;use internal_type_traits::{One,Zero};use modint_traits::{ModInt,RemEuclidU32};use std::fmt::Display;use std::iter::{Product,Sum};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use std::str::FromStr;pub type ModInt998244353=StaticModInt<998244353>;pub type ModInt1000000007=StaticModInt<1000000007>;#[derive(Debug,Clone,Copy,PartialEq,Eq,Hash,Default)]pub struct StaticModInt<const MOD:u32>{value:u32,}impl<const MOD:u32>Zero for StaticModInt<MOD>{fn zero()->Self{Self::raw(0)}}impl<const MOD:u32>One for StaticModInt<MOD>{fn one()->Self{Self::new(1)}}impl<const MOD:u32>Display for StaticModInt<MOD>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl<const MOD:u32,T>Sum<T>for StaticModInt<MOD>where Self:Add<T,Output=Self>,{fn sum<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::raw(0),Add::add)}}impl<const MOD:u32,T>Product<T>for StaticModInt<MOD>where Self:Mul<T,Output=Self>,{fn product<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::new(1),Mul::mul)}}impl<const MOD:u32>FromStr for StaticModInt<MOD>{type Err=<i64 as FromStr>::Err;fn from_str(s:&str)->Result<Self,Self::Err>{i64::from_str(s).map(Self::new)}}impl<const MOD:u32>StaticModInt<MOD>{#[inline]pub fn value(&self)->u32{self.value}#[inline]pub fn modulus()->u32{MOD}#[inline]pub fn new<T:RemEuclidU32>(x:T)->Self{ModInt::new(x)}#[inline]pub fn raw(x:u32)->Self{Self{value:x}}#[inline]pub fn pow(&self,n:u64)->Self{ModInt::pow(self,n)}#[inline]pub fn inv(&self)->Self{ModInt::inv(self)}}impl<const MOD:u32>ModInt for StaticModInt<MOD>{#[inline]fn value(&self)->u32{self.value}#[inline]fn modulus()->u32{MOD}#[inline]fn raw(x:u32)->Self{Self{value:x}}#[inline]fn new<T:RemEuclidU32>(x:T)->Self{Self{value:x.rem_euclid_u32(MOD),}}}impl<const MOD:u32>Neg for StaticModInt<MOD>{type Output=Self;#[inline]fn neg(self)->Self{if self.value==0{Self{value:0}}else{Self{value:MOD-self.value,}}}}macro_rules!impl_ops{($trait:ident,$method:ident,$assign_trait:ident,$assign_method:ident)=>{impl<const MOD:u32,T>$trait<T>for StaticModInt<MOD>where Self:$assign_trait<T>,{type Output=Self;fn$method(mut self,rhs:T)->Self{StaticModInt::<MOD>::$assign_method(&mut self,rhs);self}}impl<const MOD:u32,T:RemEuclidU32>$assign_trait<T>for StaticModInt<MOD>{fn$assign_method(&mut self,rhs:T){StaticModInt::<MOD>::$assign_method(self,Self::new(rhs));}}};}impl_ops!(Add,add,AddAssign,add_assign);impl_ops!(Sub,sub,SubAssign,sub_assign);impl_ops!(Mul,mul,MulAssign,mul_assign);impl_ops!(Div,div,DivAssign,div_assign);impl<const MOD:u32>AddAssign for StaticModInt<MOD>{fn add_assign(&mut self,rhs:Self){self.value+=rhs.value;if self.value>=MOD{self.value-=MOD;}}}impl<const MOD:u32>SubAssign for StaticModInt<MOD>{fn sub_assign(&mut self,rhs:Self){if self.value<rhs.value{self.value+=MOD;}self.value-=rhs.value;}}impl<const MOD:u32>MulAssign for StaticModInt<MOD>{fn mul_assign(&mut self,rhs:Self){self.value=(self.value as u64*rhs.value as u64).rem_euclid_u32(MOD);}}#[allow(clippy::suspicious_op_assign_impl)]impl<const MOD:u32>DivAssign for StaticModInt<MOD>{fn div_assign(&mut self,rhs:Self){*self*=rhs.inv();}}macro_rules!impl_from_primitive{($($t:ty),*)=>{$(impl<const MOD:u32>From<$t>for StaticModInt<MOD>{fn from(x:$t)->Self{Self::new(x)}})*};}impl_from_primitive!(u8,u16,u32,u64,usize,u128,i8,i16,i32,i64,isize,i128);}
    }

    pub(crate) mod macros {
        pub mod bit_matrix {}
        pub mod __bitset_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __modint_traits_0_1_0 {}
        pub mod static_modint {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod bit_matrix {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__bitset_0_1_0 as bitset;}
        pub mod __bitset_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __modint_traits_0_1_0 {}
        pub mod static_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__internal_type_traits_0_1_0 as internal_type_traits,__modint_traits_0_1_0 as modint_traits};}
    }
}