// The main code is at the very bottom. #[allow(unused_imports)] use { lib::byte::ByteChar, std::cell::{Cell, RefCell}, std::cmp::{ self, Ordering::{self, *}, Reverse, }, std::collections::*, std::convert::identity, std::fmt::{self, Debug, Display, Formatter}, std::io::prelude::*, std::iter::{self, FromIterator}, std::marker::PhantomData, std::mem, std::num::Wrapping, std::ops::{Range, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive}, std::process, std::rc::Rc, std::thread, std::time::{Duration, Instant}, std::{char, f32, f64, i128, i16, i32, i64, i8, isize, str, u128, u16, u32, u64, u8, usize}, }; #[allow(unused_imports)] #[macro_use] pub mod lib { pub mod byte { pub use self::byte_char::*; mod byte_char { use std::error::Error; use std::fmt::{self, Debug, Display, Formatter}; use std::str::FromStr; #[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)] #[repr(transparent)] pub struct ByteChar(pub u8); impl Debug for ByteChar { fn fmt(&self, f: &mut Formatter) -> fmt::Result { write!(f, "b'{}'", self.0 as char) } } impl Display for ByteChar { fn fmt(&self, f: &mut Formatter) -> fmt::Result { write!(f, "{}", self.0 as char) } } impl FromStr for ByteChar { type Err = ParseByteCharError; fn from_str(s: &str) -> Result { match s.as_bytes().len() { 1 => Ok(ByteChar(s.as_bytes()[0])), 0 => Err(ParseByteCharErrorKind::EmptyStr.into()), _ => Err(ParseByteCharErrorKind::TooManyBytes.into()), } } } #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] pub struct ParseByteCharError { kind: ParseByteCharErrorKind, } impl Display for ParseByteCharError { fn fmt(&self, f: &mut Formatter) -> fmt::Result { f.write_str(match self.kind { ParseByteCharErrorKind::EmptyStr => "empty string", ParseByteCharErrorKind::TooManyBytes => "too many bytes", }) } } impl Error for ParseByteCharError {} #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] enum ParseByteCharErrorKind { EmptyStr, TooManyBytes, } impl From for ParseByteCharError { fn from(kind: ParseByteCharErrorKind) -> ParseByteCharError { ParseByteCharError { kind } } } } } pub mod io { pub use self::scanner::*; mod scanner { use std::io::{self, BufRead}; use std::iter; use std::str::FromStr; #[derive(Debug)] pub struct Scanner { reader: R, buf: String, pos: usize, } impl Scanner { pub fn new(reader: R) -> Self { Scanner { reader, buf: String::new(), pos: 0, } } pub fn next(&mut self) -> io::Result<&str> { let start = loop { match self.rest().find(|c| c != ' ') { Some(i) => break i, None => self.fill_buf()?, } }; self.pos += start; let len = self.rest().find(' ').unwrap_or(self.rest().len()); let s = &self.buf[self.pos..][..len]; // self.rest()[..len] self.pos += len; Ok(s) } pub fn parse_next(&mut self) -> io::Result> where T: FromStr, { Ok(self.next()?.parse()) } pub fn parse_next_n(&mut self, n: usize) -> io::Result, T::Err>> where T: FromStr, { iter::repeat_with(|| self.parse_next()).take(n).collect() } pub fn map_next_bytes(&mut self, mut f: F) -> io::Result> where F: FnMut(u8) -> T, { Ok(self.next()?.bytes().map(&mut f).collect()) } pub fn map_next_bytes_n(&mut self, n: usize, mut f: F) -> io::Result>> where F: FnMut(u8) -> T, { iter::repeat_with(|| self.map_next_bytes(&mut f)) .take(n) .collect() } fn rest(&self) -> &str { &self.buf[self.pos..] } fn fill_buf(&mut self) -> io::Result<()> { self.buf.clear(); self.pos = 0; let read = self.reader.read_line(&mut self.buf)?; if read == 0 { return Err(io::ErrorKind::UnexpectedEof.into()); } if *self.buf.as_bytes().last().unwrap() == b'\n' { self.buf.pop(); } Ok(()) } } } } } mod automaton_dp { use std::{collections::HashMap, hash::Hash, mem}; pub trait Monoid { fn op(&self, rhs: &Self) -> Self; fn identity() -> Self; } impl Monoid for (T0, T1) { fn op(&self, rhs: &Self) -> Self { (self.0.op(&rhs.0), self.1.op(&rhs.1)) } fn identity() -> Self { (T0::identity(), T1::identity()) } } pub trait Dfa { type Char; type State; fn initial_state(&self) -> Option; fn next_state(&self, state: &Self::State, c: &Self::Char) -> Option; fn is_accept_state(&self, state: &Self::State) -> bool; } pub fn automaton_dp( dfa: A, sigma: impl IntoIterator + Clone, len: usize, mut mul: impl FnMut(&M, &A::Char) -> M, e: M, ) -> M where A: Dfa, A::State: Eq + Hash, M: Monoid, { let mut dp = HashMap::::new(); let mut dp_next = HashMap::::new(); if let Some(initial_state) = dfa.initial_state() { dp.insert(initial_state, e); } for _ in 0..len { for (state, value) in dp.drain() { for c in sigma.clone() { if let Some(next_state) = dfa.next_state(&state, &c) { let value = mul(&value, &c); dp_next .entry(next_state) .and_modify(|acc| *acc = acc.op(&value)) .or_insert(value); } } } mem::swap(&mut dp, &mut dp_next); dp_next.clear(); } let mut acc = M::identity(); for (state, value) in dp { if dfa.is_accept_state(&state) { acc = acc.op(&value); } } acc } pub struct And(pub A0, pub A1); impl Dfa for And where A0: Dfa, A1: Dfa, { type Char = A0::Char; type State = (A0::State, A1::State); fn initial_state(&self) -> Option { match (self.0.initial_state(), self.1.initial_state()) { (Some(st0), Some(st1)) => Some((st0, st1)), _ => None, } } fn next_state(&self, state: &Self::State, c: &Self::Char) -> Option { match ( self.0.next_state(&state.0, c), self.1.next_state(&state.1, c), ) { (Some(st0), Some(st1)) => Some((st0, st1)), _ => None, } } fn is_accept_state(&self, state: &Self::State) -> bool { self.0.is_accept_state(&state.0) && self.1.is_accept_state(&state.1) } } } #[allow(unused_macros)] macro_rules! eprint { ($($arg:tt)*) => { if cfg!(debug_assertions) { std::eprint!($($arg)*) } }; } #[allow(unused_macros)] macro_rules! eprintln { ($($arg:tt)*) => { if cfg!(debug_assertions) { std::eprintln!($($arg)*) } }; } #[allow(unused_macros)] macro_rules! dbg { ($($arg:tt)*) => { if cfg!(debug_assertions) { std::dbg!($($arg)*) } else { ($($arg)*) } }; } const CUSTOM_STACK_SIZE_MIB: Option = Some(1024); const INTERACTIVE: bool = false; fn main() -> std::io::Result<()> { match CUSTOM_STACK_SIZE_MIB { Some(stack_size_mib) => std::thread::Builder::new() .name("run_solver".to_owned()) .stack_size(stack_size_mib * 1024 * 1024) .spawn(run_solver)? .join() .unwrap(), None => run_solver(), } } fn run_solver() -> std::io::Result<()> { let stdin = std::io::stdin(); let reader = stdin.lock(); let stdout = std::io::stdout(); let writer = stdout.lock(); macro_rules! with_wrapper { ($($wrapper:expr)?) => {{ let mut writer = $($wrapper)?(writer); solve(reader, &mut writer)?; writer.flush() }}; } if cfg!(debug_assertions) || INTERACTIVE { with_wrapper!() } else { with_wrapper!(std::io::BufWriter::new) } } fn solve(reader: R, mut writer: W) -> std::io::Result<()> where R: BufRead, W: Write, { let mut _scanner = lib::io::Scanner::new(reader); #[allow(unused_macros)] macro_rules! scan { ($T:ty) => { _scanner.parse_next::<$T>()?.unwrap() }; ($($T:ty),+) => { ($(scan!($T)),+) }; ($T:ty; $n:expr) => { _scanner.parse_next_n::<$T>($n)?.unwrap() }; ($($T:ty),+; $n:expr) => { iter::repeat_with(|| -> std::io::Result<_> { Ok(($(scan!($T)),+)) }) .take($n) .collect::>>()? }; } #[allow(unused_macros)] macro_rules! scan_bytes_map { ($f:expr) => { _scanner.map_next_bytes($f)? }; ($f:expr; $n:expr) => { _scanner.map_next_bytes_n($n, $f)? }; } #[allow(unused_macros)] macro_rules! print { ($($arg:tt)*) => { write!(writer, $($arg)*)? }; } #[allow(unused_macros)] macro_rules! println { ($($arg:tt)*) => { writeln!(writer, $($arg)*)? }; } #[allow(unused_macros)] macro_rules! answer { ($($arg:tt)*) => {{ println!($($arg)*); return Ok(()); }}; } { use automaton_dp::*; const MOD: u64 = 998244353; #[derive(Clone, Copy)] struct ModSum(u64); impl Monoid for ModSum { fn op(&self, rhs: &Self) -> Self { let mut sum = self.0 + rhs.0; if sum >= MOD { sum -= MOD; } ModSum(sum) } fn identity() -> Self { ModSum(0) } } #[derive(Clone)] struct GoodXor(RangeInclusive); impl Dfa for GoodXor { type Char = u32; type State = u32; fn initial_state(&self) -> Option { Some(0) } fn next_state(&self, s: &u32, c: &u32) -> Option { Some(s ^ c) } fn is_accept_state(&self, s: &u32) -> bool { self.0.contains(s) } } #[derive(Clone)] struct LocallyDistinct; impl Dfa for LocallyDistinct { type Char = u32; type State = Option; fn initial_state(&self) -> Option> { Some(None) } fn next_state(&self, s: &Option, c: &u32) -> Option> { if *s != Some(*c) { Some(Some(*c)) } else { None } } fn is_accept_state(&self, _: &Option) -> bool { true } } let (n, k, x, y) = scan!(usize, usize, u32, u32); let mut a = scan!(u32; k); a.sort_unstable(); a.dedup(); let dfa = And(GoodXor(x..=y), LocallyDistinct); let ans = automaton_dp(dfa, a.iter().copied(), n, |x, _| *x, ModSum(1)); println!("{}", ans.0); } #[allow(unreachable_code)] Ok(()) }