use std::marker::*; use std::ops::*; pub trait Modulo { fn modulo() -> u32; } pub struct ConstantModulo; impl Modulo for ConstantModulo<{ M }> { fn modulo() -> u32 { M } } pub struct ModInt(u32, PhantomData); impl Clone for ModInt { fn clone(&self) -> Self { Self::new_unchecked(self.0) } } impl Copy for ModInt {} impl Add for ModInt { type Output = ModInt; fn add(self, rhs: Self) -> Self::Output { let mut v = self.0 + rhs.0; if v >= T::modulo() { v -= T::modulo(); } Self::new_unchecked(v) } } impl AddAssign for ModInt { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl Sub for ModInt { type Output = ModInt; fn sub(self, rhs: Self) -> Self::Output { let mut v = self.0 - rhs.0; if self.0 < rhs.0 { v += T::modulo(); } Self::new_unchecked(v) } } impl SubAssign for ModInt { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl Mul for ModInt { type Output = ModInt; fn mul(self, rhs: Self) -> Self::Output { let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64; Self::new_unchecked(v as u32) } } impl MulAssign for ModInt { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl Neg for ModInt { type Output = ModInt; fn neg(self) -> Self::Output { if self.is_zero() { Self::zero() } else { Self::new_unchecked(T::modulo() - self.0) } } } impl std::fmt::Display for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::fmt::Debug for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl Default for ModInt { fn default() -> Self { Self::zero() } } impl std::str::FromStr for ModInt { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result { let val = s.parse::()?; Ok(ModInt::new(val)) } } impl From for ModInt { fn from(val: usize) -> ModInt { ModInt::new_unchecked((val % T::modulo() as usize) as u32) } } impl From for ModInt { fn from(val: u64) -> ModInt { ModInt::new_unchecked((val % T::modulo() as u64) as u32) } } impl ModInt { pub fn new_unchecked(n: u32) -> Self { ModInt(n, PhantomData) } pub fn zero() -> Self { ModInt::new_unchecked(0) } pub fn one() -> Self { ModInt::new_unchecked(1) } pub fn is_zero(&self) -> bool { self.0 == 0 } } impl ModInt { pub fn new(d: u32) -> Self { ModInt::new_unchecked(d % T::modulo()) } pub fn pow(&self, mut n: u64) -> Self { let mut t = Self::one(); let mut s = *self; while n > 0 { if n & 1 == 1 { t *= s; } s *= s; n >>= 1; } t } pub fn inv(&self) -> Self { assert!(!self.is_zero()); self.pow(T::modulo() as u64 - 2) } } type M = ModInt>; fn read() -> (i32, i32, i32, i32, i32, i32) { let mut s = String::new(); use std::io::Read; std::io::stdin().read_to_string(&mut s).unwrap(); let a = s.trim().split_whitespace().flat_map(|s| s.parse()).collect::>(); (a[0], a[1], a[2], a[3], a[4], a[5]) } fn main() { let (t, a, b, c, d, e) = read(); type Map = std::collections::HashMap; let mut dp = Map::new(); dp.insert(0, M::one()); for _ in 0..t { let mut next = Map::new(); for (x, w) in dp { for d in [a, -a, b, -b, c, -c].iter() { *next.entry(x + *d).or_default() += w; } } dp = next; } let ans = dp.into_iter().filter(|p| d <= p.0 && p.0 <= e).fold(M::zero(), |s, p| s + p.1); println!("{}", ans); }