fn read() -> (usize, Vec) { use std::io::*; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let mut next = || it.next().unwrap(); let n: usize = next().parse().unwrap(); let m: usize = next().parse().unwrap(); (m, (0..n).flat_map(|_| next().parse()).collect()) } fn main() { let (mut m, a) = read(); const MOD: u32 = 1_234_567_891; let mut dp = vec![1]; let mut next = vec![]; while m > 0 { for &a in a.iter() { next.clear(); next.resize(dp.len() + a, 0); next[..dp.len()].clone_from_slice(&dp); for (next, dp) in next[a..].iter_mut().zip(dp.iter()) { let v = *next + *dp; *next = if v >= MOD { v - MOD } else { v }; } std::mem::swap(&mut dp, &mut next); } next.clear(); for dp in dp.iter().skip(m & 1).step_by(2) { next.push(*dp); } std::mem::swap(&mut dp, &mut next); m >>= 1; } println!("{}", dp[0]); }