#![allow(unused_imports, unused_macros, dead_code)] macro_rules! min { (.. $x:expr) => {{ let mut it = $x.iter(); it.next().map(|z| it.fold(z, |x, y| min!(x, y))) }}; ($x:expr) => ($x); ($x:expr, $($ys:expr),*) => {{ let t = min!($($ys),*); if $x < t { $x } else { t } }} } macro_rules! max { (.. $x:expr) => {{ let mut it = $x.iter(); it.next().map(|z| it.fold(z, |x, y| max!(x, y))) }}; ($x:expr) => ($x); ($x:expr, $($ys:expr),*) => {{ let t = max!($($ys),*); if $x > t { $x } else { t } }} } macro_rules! trace { ($x:expr) => { #[cfg(debug_assertions)] eprintln!(">>> {} = {:?}", stringify!($x), $x) }; ($($xs:expr),*) => { trace!(($($xs),*)) } } macro_rules! flush { () => { std::io::stdout().flush().unwrap(); }; } macro_rules! put { (.. $x:expr) => {{ let mut it = $x.iter(); if let Some(x) = it.next() { print!("{}", x); } for x in it { print!(" {}", x); } println!(""); }}; ($x:expr) => { println!("{}", $x) }; ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) } } const M: i64 = 1_000_000_007; macro_rules! mint { ($x:expr) => { ModInt::new($x, MOD_998244353) }; } fn main() { let mut sc = Scanner::new(); let n: usize = sc.cin(); let k: usize = sc.cin(); let x: u64 = sc.cin(); let y: u64 = sc.cin(); let xs: Vec = sc.vec(k); if x >= 1024 { put!(0); return; } let y = min!(y + 1, 1024); let required = x..y; let xs = dup(xs); let k = xs.len(); let mut t = DefaultDict::new(0); for p in PowerPermutation::new(k, n / 2) { let mut ok = true; for i in 1..n / 2 { if p[i - 1] == p[i] { ok = false } } if !ok { continue; } let mut s = 0; let last = xs[p[0]]; for i in 0..n / 2 { s ^= xs[p[i]]; } t[(s, last)] += 1; } let mut ans = mint!(0); for (&(s, last), k) in t.iter() { for x in required.clone() { for b in 0..1024 { if b == last { continue; } ans += k * t[(s ^ x, b)]; } } } put!(ans); } /// 重複排除 fn dup(xs: Vec) -> Vec { use std::collections::BTreeSet; xs.iter() .cloned() .collect::>() .iter() .cloned() .collect() } // @collections/defaultdict #[derive(Debug, Clone)] pub struct DefaultDict where K: Eq + std::hash::Hash, { data: std::collections::HashMap, default: V, } impl DefaultDict { pub fn new(default: V) -> DefaultDict { DefaultDict { data: std::collections::HashMap::new(), default, } } pub fn keys(&self) -> std::collections::hash_map::Keys { self.data.keys() } pub fn iter(&self) -> std::collections::hash_map::Iter { self.data.iter() } pub fn len(&self) -> usize { self.data.len() } } impl std::ops::Index for DefaultDict { type Output = V; fn index(&self, key: K) -> &Self::Output { if let Some(val) = self.data.get(&key) { val } else { &self.default } } } impl std::ops::IndexMut for DefaultDict { fn index_mut(&mut self, key: K) -> &mut Self::Output { let val = self.default.clone(); self.data.entry(key.clone()).or_insert(val); self.data.get_mut(&key).unwrap() } } // @num/iter/power pub struct PowerPermutation { n: usize, m: usize, ar: Vec, } impl PowerPermutation { pub fn new(n: usize, m: usize) -> PowerPermutation { let ar = vec![0; m]; PowerPermutation { n: n, m: m, ar: ar } } } impl Iterator for PowerPermutation { type Item = Vec; fn next(&mut self) -> Option> { if self.ar[self.m - 1] >= self.n { return None; } let r = self.ar.clone(); self.ar[0] += 1; for i in 0..self.m - 1 { if self.ar[i] == self.n { self.ar[i] = 0; self.ar[i + 1] += 1; } else { break; } } return Some(r); } } // @algebra/modint #[derive(Debug, PartialEq, Eq, Clone, Copy)] pub struct ModInt(pub i64, pub i64); // (residual, modulo) pub const MOD_1000000007: i64 = 1_000_000_007; pub const MOD_998244353: i64 = 998_244_353; impl ModInt { pub fn new(residual: i64, modulo: i64) -> ModInt { if residual >= modulo { ModInt(residual % modulo, modulo) } else if residual < 0 { ModInt((residual % modulo) + modulo, modulo) } else { ModInt(residual, modulo) } } pub fn unwrap(self) -> i64 { self.0 } pub fn inv(self) -> Self { fn exgcd(r0: i64, a0: i64, b0: i64, r: i64, a: i64, b: i64) -> (i64, i64, i64) { if r > 0 { exgcd(r, a, b, r0 % r, a0 - r0 / r * a, b0 - r0 / r * b) } else { (a0, b0, r0) } } let (a, _, r) = exgcd(self.0, 1, 0, self.1, 0, 1); if r != 1 { panic!("{:?} has no inverse!", self); } ModInt(((a % self.1) + self.1) % self.1, self.1) } pub fn pow(self, n: i64) -> Self { if n < 0 { self.pow(-n).inv() } else if n == 0 { ModInt(1, self.1) } else if n == 1 { self } else { let mut x = (self * self).pow(n / 2); if n % 2 == 1 { x *= self } x } } } impl std::fmt::Display for ModInt { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::ops::Neg for ModInt { type Output = Self; fn neg(self) -> Self { if self.0 == 0 { return self; } ModInt(self.1 - self.0, self.1) } } impl std::ops::Add for ModInt { type Output = Self; fn add(self, other: i64) -> Self { ModInt::new(self.0 + other, self.1) } } impl std::ops::Add for ModInt { type Output = Self; fn add(self, other: ModInt) -> Self { self + other.0 } } impl std::ops::Add for i64 { type Output = ModInt; fn add(self, other: ModInt) -> ModInt { other + self } } impl std::ops::AddAssign for ModInt { fn add_assign(&mut self, other: i64) { self.0 = ModInt::new(self.0 + other, self.1).0; } } impl std::ops::AddAssign for ModInt { fn add_assign(&mut self, other: ModInt) { *self += other.0; } } impl std::ops::Sub for ModInt { type Output = Self; fn sub(self, other: i64) -> Self { ModInt::new(self.0 - other, self.1) } } impl std::ops::Sub for ModInt { type Output = Self; fn sub(self, other: ModInt) -> Self { self - other.0 } } impl std::ops::Sub for i64 { type Output = ModInt; fn sub(self, other: ModInt) -> ModInt { ModInt::new(self - other.0, other.1) } } impl std::ops::SubAssign for ModInt { fn sub_assign(&mut self, other: i64) { self.0 = ModInt::new(self.0 - other, self.1).0; } } impl std::ops::SubAssign for ModInt { fn sub_assign(&mut self, other: ModInt) { *self -= other.0; } } impl std::ops::Mul for ModInt { type Output = Self; fn mul(self, other: i64) -> Self { ModInt::new(self.0 * other, self.1) } } impl std::ops::Mul for ModInt { type Output = Self; fn mul(self, other: ModInt) -> Self { self * other.0 } } impl std::ops::Mul for i64 { type Output = ModInt; fn mul(self, other: ModInt) -> ModInt { other * self } } impl std::ops::MulAssign for ModInt { fn mul_assign(&mut self, other: i64) { self.0 = ModInt::new(self.0 * other, self.1).0; } } impl std::ops::MulAssign for ModInt { fn mul_assign(&mut self, other: ModInt) { *self *= other.0; } } impl std::ops::Div for ModInt { type Output = Self; fn div(self, other: ModInt) -> Self { self * other.inv() } } impl std::ops::Div for ModInt { type Output = Self; fn div(self, other: i64) -> Self { self / ModInt::new(other, self.1) } } impl std::ops::Div for i64 { type Output = ModInt; fn div(self, other: ModInt) -> ModInt { other.inv() * self } } impl std::ops::DivAssign for ModInt { fn div_assign(&mut self, other: ModInt) { self.0 = (self.clone() / other).0; } } impl std::ops::DivAssign for ModInt { fn div_assign(&mut self, other: i64) { *self /= ModInt(other, self.1); } } use std::collections::VecDeque; use std::io::{self, Write}; use std::str::FromStr; struct Scanner { stdin: io::Stdin, buffer: VecDeque, } impl Scanner { fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new(), } } fn cin(&mut self) -> T { while self.buffer.is_empty() { let mut line = String::new(); let _ = self.stdin.read_line(&mut line); for w in line.split_whitespace() { self.buffer.push_back(String::from(w)); } } self.buffer.pop_front().unwrap().parse::().ok().unwrap() } fn chars(&mut self) -> Vec { self.cin::().chars().collect() } fn vec(&mut self, n: usize) -> Vec { (0..n).map(|_| self.cin()).collect() } }