type Fp = fp::Fp<1_000_000_007>; fn main() { let n: usize = io::input(); let (a, b, c, min, max): (isize, isize, isize, isize, isize) = io::input(); let a = a.unsigned_abs(); let b = b.unsigned_abs(); let c = c.unsigned_abs(); let shift = a.max(b).max(c) * n; let min = shift.saturating_add_signed(min).min(2 * shift); let max = shift.saturating_add_signed(max).min(2 * shift); let mut dp = vec![Fp::new(0); 2 * shift + 1]; dp[shift as usize] = Fp::new(1); for _ in 0..n { let mut swp = vec![Fp::new(0); 2 * shift + 1]; for i in 0..=2 * shift { let p = dp[i]; for j in [ Some(i + a).filter(|&j| j <= 2 * shift), Some(i + b).filter(|&j| j <= 2 * shift), Some(i + c).filter(|&j| j <= 2 * shift), i.checked_sub(a), i.checked_sub(b), i.checked_sub(c), ] .iter() .flatten() { swp[*j as usize] += p; } } dp = swp; } let ans = dp[min..=max].iter().sum::(); println!("{}", ans); } // io {{{ // https://ngtkana.github.io/ac-adapter-rs/io/index.html #[allow(dead_code)] mod io { use std::cell::Cell; use std::io::stdin; use std::io::BufRead; use std::io::BufReader; use std::io::Lines; use std::io::Stdin; use std::sync::Mutex; use std::sync::Once; pub fn input() -> T { ParseLine::parse_line(&line()) } pub trait ParseLine { fn parse_line(s: &str) -> Self; } macro_rules! impl_parse_line { ($($t:ty),*) => { $(impl ParseLine for $t { fn parse_line(s: &str) -> Self { s.parse().unwrap() } })* }; } impl_parse_line!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, String, char); macro_rules! impl_parse_line_tuple { ($($t:ident),*) => { impl<$($t: ParseLine),*> ParseLine for ($($t,)*) { fn parse_line(s: &str) -> Self { let mut s = s.split_whitespace(); ($($t::parse_line(s.next().unwrap()),)*) } } }; } impl_parse_line_tuple!(T0, T1); impl_parse_line_tuple!(T0, T1, T2); impl_parse_line_tuple!(T0, T1, T2, T3); impl_parse_line_tuple!(T0, T1, T2, T3, T4); impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5); impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6); impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6, T7); impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6, T7, T8); impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6, T7, T8, T9); impl ParseLine for Vec { fn parse_line(s: &str) -> Self { s.split_whitespace().map(T::parse_line).collect() } } static ONCE: Once = Once::new(); type Server = Mutex>>; struct Lazy(Cell>); unsafe impl Sync for Lazy {} fn line() -> String { static SYNCER: Lazy = Lazy(Cell::new(None)); ONCE.call_once(|| { SYNCER .0 .set(Some(Mutex::new(BufReader::new(stdin()).lines()))); }); unsafe { (*SYNCER.0.as_ptr()) .as_ref() .unwrap() .lock() .unwrap() .next() .unwrap() .unwrap() } } } // }}} // fp {{{ // https://ngtkana.github.io/ac-adapter-rs/fp/index.html #[allow(dead_code)] mod fp { mod ext_gcd { pub(crate) fn mod_inv(x: u64) -> u64 { debug_assert!(P % 2 == 1); debug_assert!(P < 1 << 31); debug_assert!(x < P); mod_inv_signed(x as i64, P as i64) as u64 } fn mod_inv_signed(a: i64, m: i64) -> i64 { debug_assert!(a > 0); debug_assert!(m > 0); if a == 1 { return 1; } m + (1 - m * mod_inv_signed(m % a, a)) / a } } mod factorial { use super::Fp; use std::ops::Index; pub struct Factorial { fact: Vec>, inv_fact: Vec>, } impl Factorial

{ pub fn new(length: usize) -> Self { let mut fact = vec![Fp::

::new(1); length + 1]; let mut inv_fact = vec![Fp::

::new(1); length + 1]; for i in 1..=length { fact[i] = fact[i - 1] * Fp::

::new(i as u64); } inv_fact[length] = fact[length].inv(); for i in (1..=length).rev() { inv_fact[i - 1] = inv_fact[i] * Fp::

::new(i as u64); } Self { fact, inv_fact } } pub fn fact(&self, n: usize) -> Fp

{ self.fact[n] } pub fn inv_fact(&self, n: usize) -> Fp

{ self.inv_fact[n] } pub fn perm(&self, n: usize, k: usize) -> Fp

{ self.fact[n] * self.inv_fact[n - k] } pub fn comb(&self, n: usize, k: usize) -> Fp

{ self.fact[n] * self.inv_fact[n - k] * self.inv_fact[k] } pub fn binom(&self, n: usize, k: usize) -> Fp

{ self.comb(n, k) } pub fn comb_or_zero(&self, n: usize, k: isize) -> Fp

{ if k < 0 || k as usize > n { Fp::

::new(0) } else { self.comb(n, k as usize) } } pub fn comb_with_reputation(&self, n: usize, k: usize) -> Fp

{ assert!(n > 0 || k > 0); self.comb(n + k - 1, k) } } impl Index for Factorial

{ type Output = Fp

; fn index(&self, index: usize) -> &Self::Output { &self.fact[index] } } } mod fourier { use super::mod_inv; use super::Fp; use super::PrimitiveRoot; const P1: u64 = 924844033; const P2: u64 = 998244353; const P3: u64 = 1012924417; type F1 = Fp; type F2 = Fp; type F3 = Fp; pub fn fps_mul(a: impl AsRef<[Fp

]>, b: impl AsRef<[Fp

]>) -> Vec> where (): PrimitiveRoot

, { let a = a.as_ref(); let b = b.as_ref(); if a.is_empty() || b.is_empty() { return vec![]; } let mut a = a.to_vec(); let mut b = b.to_vec(); let n = a.len() + b.len() - 1; let len = n.next_power_of_two(); a.resize(len, Fp::new(0)); b.resize(len, Fp::new(0)); fft(&mut a); fft(&mut b); for (a, b) in a.iter_mut().zip(b.iter()) { *a *= *b; } ifft(&mut a); a.truncate(n); a } pub fn any_mod_fps_mul(a: &[Fp

], b: &[Fp

]) -> Vec> { let v1 = fps_mul( a.iter().map(|&x| F1::new(x.value())).collect::>(), b.iter().map(|&x| F1::new(x.value())).collect::>(), ); let v2 = fps_mul( a.iter().map(|&x| F2::new(x.value())).collect::>(), b.iter().map(|&x| F2::new(x.value())).collect::>(), ); let v3 = fps_mul( a.iter().map(|&x| F3::new(x.value())).collect::>(), b.iter().map(|&x| F3::new(x.value())).collect::>(), ); v1.into_iter() .zip(v2) .zip(v3) .map(|((e1, e2), e3)| garner(e1, e2, e3)) .collect::>() } pub fn fft(f: &mut [Fp

]) where (): PrimitiveRoot

, { let n = f.len(); assert!(n.is_power_of_two()); assert!((P - 1) % n as u64 == 0); let mut root = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / f.len() as u64); let fourth = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / 4); let mut fft_len = n; while 4 <= fft_len { let quarter = fft_len / 4; for f in f.chunks_mut(fft_len) { let mut c = Fp::new(1); for (((i, j), k), l) in (0..) .zip(quarter..) .zip(quarter * 2..) .zip(quarter * 3..) .take(quarter) { let c2 = c * c; let x = f[i] + f[k]; let y = f[j] + f[l]; let z = f[i] - f[k]; let w = fourth * (f[j] - f[l]); f[i] = x + y; f[j] = c2 * (x - y); f[k] = c * (z + w); f[l] = c2 * c * (z - w); c *= root; } } root *= root; root *= root; fft_len = quarter; } if fft_len == 2 { for f in f.chunks_mut(2) { let x = f[0]; let y = f[1]; f[0] = x + y; f[1] = x - y; } } } pub fn ifft(f: &mut [Fp

]) where (): PrimitiveRoot

, { let n = f.len(); assert!(n.is_power_of_two()); let root = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / f.len() as u64); let mut roots = std::iter::successors(Some(root.inv()), |x| Some(x * x)) .take(n.trailing_zeros() as usize + 1) .collect::>(); roots.reverse(); let fourth = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / 4).inv(); let mut quarter = 1_usize; if n.trailing_zeros() % 2 == 1 { for f in f.chunks_mut(2) { let x = f[0]; let y = f[1]; f[0] = x + y; f[1] = x - y; } quarter = 2; } while quarter != n { let fft_len = quarter * 4; let root = roots[fft_len.trailing_zeros() as usize]; for f in f.chunks_mut(fft_len) { let mut c = Fp::new(1); for (((i, j), k), l) in (0..) .zip(quarter..) .zip(quarter * 2..) .zip(quarter * 3..) .take(quarter) { let c2 = c * c; let x = f[i] + c2 * f[j]; let y = f[i] - c2 * f[j]; let z = c * (f[k] + c2 * f[l]); let w = fourth * c * (f[k] - c2 * f[l]); f[i] = x + z; f[j] = y + w; f[k] = x - z; f[l] = y - w; c *= root; } } quarter = fft_len; } let d = Fp::from(f.len()).inv(); f.iter_mut().for_each(|x| *x *= d); } fn garner(x1: Fp, x2: Fp, x3: Fp) -> Fp

{ let (x1, x2, x3) = (x1.value(), x2.value(), x3.value()); let x2 = ((x2 + (P2 - x1)) * mod_inv::(P1)) % P2; let x3 = (((x3 + (P3 - x1)) * mod_inv::(P1) % P3 + (P3 - x2)) * mod_inv::(P2)) % P3; Fp::new(x1 + P1 * (x2 + P2 * x3 % P)) } } use ext_gcd::mod_inv; pub use factorial::Factorial; pub use fourier::any_mod_fps_mul; pub use fourier::fft; pub use fourier::fps_mul; pub use fourier::ifft; use std::iter::Product; use std::iter::Sum; use std::mem::swap; use std::ops::Add; use std::ops::AddAssign; use std::ops::Div; use std::ops::DivAssign; use std::ops::Mul; use std::ops::MulAssign; use std::ops::Neg; use std::ops::Sub; use std::ops::SubAssign; #[macro_export] macro_rules! fp { ($value:expr) => { $crate::fp::Fp::from($value) }; ($value:expr; mod $p:expr) => { $crate::fp::Fp::<$p>::from($value) }; } pub trait PrimitiveRoot { const VALUE: Fp

; } impl PrimitiveRoot<998244353> for () { const VALUE: Fp<998244353> = Fp::new(3); } impl PrimitiveRoot<1012924417> for () { const VALUE: Fp<1012924417> = Fp::new(5); } impl PrimitiveRoot<924844033> for () { const VALUE: Fp<924844033> = Fp::new(5); } #[derive(Clone, Copy, PartialEq, Eq, Hash)] pub struct Fp { value: u64, } impl Fp

{ pub const fn new(value: u64) -> Self { Self { value: value % P } } pub const fn value(self) -> u64 { self.value } pub fn inv(self) -> Self { Self { value: mod_inv::

(self.value), } } pub fn pow(self, mut exp: u64) -> Self { let mut result = Self::new(1); let mut base = self; while exp > 0 { if exp & 1 == 1 { result *= base; } base *= base; exp >>= 1; } result } pub fn sign(pow: usize) -> Self { Self::new(if pow % 2 == 0 { 1 } else { P - 1 }) } } impl std::fmt::Debug for Fp

{ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { pub fn berlekamp_massey_fp(a: i64, p: i64) -> [i64; 2] { let mut u0 = 0_i64; let mut v0 = 1_i64; let mut w0 = a * u0 + p * v0; let mut u1 = 1_i64; let mut v1 = 0_i64; let mut w1 = a * u1 + p * v1; while p <= w0 * w0 { let q = w0 / w1; u0 -= q * u1; v0 -= q * v1; w0 -= q * w1; swap(&mut u0, &mut u1); swap(&mut v0, &mut v1); swap(&mut w0, &mut w1); } [w0, u0] } if self.value == 0 { return write!(f, "0"); } let [mut num, mut den] = berlekamp_massey_fp(self.value as i64, P as i64); if den < 0 { num = -num; den = -den; } if den == 1 { write!(f, "{}", num) } else { write!(f, "{}/{}", num, den) } } } impl std::fmt::Display for Fp

{ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.value()) } } macro_rules! impl_from_signed { ($($t:ty),*) => { $( impl From<$t> for Fp

{ fn from(x: $t) -> Self { if x < 0 { -Self::new((P as i64 - x as i64) as u64) } else { Self::new(x as u64) } } } )* }; } impl_from_signed!(i8, i16, i32, i64, i128, isize); macro_rules! impl_from_unsigned { ($($t:ty),*) => { $( impl From<$t> for Fp

{ fn from(x: $t) -> Self { Self::new(x as u64) } } )* }; } impl_from_unsigned!(u8, u16, u32, u64, u128, usize); impl AddAssign> for Fp

{ fn add_assign(&mut self, rhs: Fp

) { self.value += rhs.value; if self.value >= P { self.value -= P; } } } impl SubAssign> for Fp

{ fn sub_assign(&mut self, rhs: Fp

) { if self.value < rhs.value { self.value += P; } self.value -= rhs.value; } } impl MulAssign> for Fp

{ fn mul_assign(&mut self, rhs: Fp

) { self.value = self.value * rhs.value % P; } } #[allow(clippy::suspicious_op_assign_impl)] impl DivAssign> for Fp

{ fn div_assign(&mut self, rhs: Fp

) { *self *= rhs.inv() } } macro_rules! fp_forward_ops { ($( $trait:ident, $trait_assign:ident, $fn:ident, $fn_assign:ident, )*) => {$( impl $trait_assign<&Fp

> for Fp

{ fn $fn_assign(&mut self, rhs: &Fp

) { self.$fn_assign(*rhs); } } impl>> $trait for Fp

{ type Output = Fp

; fn $fn(mut self, rhs: T) -> Self::Output { self.$fn_assign(rhs.into()); self } } impl $trait<&Fp

> for Fp

{ type Output = Fp

; fn $fn(self, rhs: &Fp

) -> Self::Output { self.$fn(*rhs) } } impl>> $trait for &Fp

{ type Output = Fp

; fn $fn(self, rhs: T) -> Self::Output { (*self).$fn(rhs.into()) } } impl $trait<&Fp

> for &Fp

{ type Output = Fp

; fn $fn(self, rhs: &Fp

) -> Self::Output { (*self).$fn(*rhs) } } )*}; } fp_forward_ops! { Add, AddAssign, add, add_assign, Sub, SubAssign, sub, sub_assign, Mul, MulAssign, mul, mul_assign, Div, DivAssign, div, div_assign, } impl Neg for Fp

{ type Output = Fp

; fn neg(mut self) -> Self::Output { if self.value > 0 { self.value = P - self.value; } self } } impl Sum for Fp

{ fn sum>(iter: I) -> Self { iter.fold(Self::new(0), |acc, x| acc + x) } } impl<'a, const P: u64> Sum<&'a Self> for Fp

{ fn sum>(iter: I) -> Self { iter.copied().sum() } } impl Product for Fp

{ fn product>(iter: I) -> Self { iter.fold(Self::new(1), |acc, x| acc * x) } } impl<'a, const P: u64> Product<&'a Self> for Fp

{ fn product>(iter: I) -> Self { iter.copied().product() } } } // }}}