#![allow(non_snake_case)] #![allow(dead_code)] #![allow(unused_macros)] #![allow(unused_imports)] use std::str::FromStr; use std::io::*; use std::collections::*; use std::cmp::*; struct Scanner> { iter: std::iter::Peekable, } macro_rules! exit { () => {{ exit!(0) }}; ($code:expr) => {{ if cfg!(local) { writeln!(std::io::stderr(), "===== Terminated =====") .expect("failed printing to stderr"); } std::process::exit($code); }} } impl> Scanner { pub fn new(iter: I) -> Scanner { Scanner { iter: iter.peekable(), } } pub fn safe_get_token(&mut self) -> Option { let token = self.iter .by_ref() .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect::(); if token.is_empty() { None } else { Some(token) } } pub fn token(&mut self) -> String { self.safe_get_token().unwrap_or_else(|| exit!()) } pub fn get(&mut self) -> T { self.token().parse::().unwrap_or_else(|_| exit!()) } pub fn vec(&mut self, len: usize) -> Vec { (0..len).map(|_| self.get()).collect() } pub fn mat(&mut self, row: usize, col: usize) -> Vec> { (0..row).map(|_| self.vec(col)).collect() } pub fn char(&mut self) -> char { self.iter.next().unwrap_or_else(|| exit!()) } pub fn chars(&mut self) -> Vec { self.get::().chars().collect() } pub fn mat_chars(&mut self, row: usize) -> Vec> { (0..row).map(|_| self.chars()).collect() } pub fn line(&mut self) -> String { if self.peek().is_some() { self.iter .by_ref() .take_while(|&c| !(c == '\n' || c == '\r')) .collect::() } else { exit!(); } } pub fn peek(&mut self) -> Option<&char> { self.iter.peek() } } use std::ops::*; use std::fmt; #[derive(Copy, Clone, PartialEq, Debug)] struct ModInt(usize); const MOD: usize = 1000000007; impl ModInt { fn pow(self, power: usize) -> Self { if power == 0 { return ModInt(1); } if power % 2 == 0 { let t = self.pow(power/2); return t * t; } self * self.pow(power-1) } fn inv(self) -> Self { self.pow(MOD - 2) } } impl Add for ModInt { type Output = Self; fn add(self, rhs: Self) -> Self { let mut tmp = self; tmp.0 += rhs.0; if tmp.0 >= MOD { tmp.0 -= MOD; } tmp } } impl AddAssign for ModInt { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl Sub for ModInt { type Output = Self; fn sub(self, rhs: Self) -> Self { let mut ret = self; if ret.0 < rhs.0 { ret.0 += MOD; } ret.0 -= rhs.0; ret } } impl SubAssign for ModInt { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl Mul for ModInt { type Output = Self; fn mul(self, rhs: ModInt) -> Self { let mut ret = self; ret.0 *= rhs.0; ret.0 %= MOD; ret } } impl MulAssign for ModInt { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl Div for ModInt { type Output = ModInt; fn div(self, rhs: ModInt) -> Self { let mut ret = self; ret.0 *= rhs.inv().0; ret.0 %= MOD; ret } } impl DivAssign for ModInt { fn div_assign(&mut self, rhs: Self) { *self = *self / rhs; } } impl fmt::Display for ModInt { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{}", self.0) } } const MAX: usize = 100 * 1000; fn main() { let cin = stdin(); let cin = cin.lock(); let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char)); let N: usize = sc.get(); let M: usize = sc.get(); let V: Vec = sc.vec(N); let R: Vec = sc.vec(N); let A: usize = sc.get(); let B: usize = sc.get(); let mut dp_v = vec![ModInt(0); MAX+1]; dp_v[0] = ModInt(1); for i in 0..N { for v in (0..MAX+1).rev() { if v >= V[i] { let prev = dp_v[v - V[i]]; dp_v[v] += prev; } } } let mut cum = vec![ModInt(0); MAX+2]; for i in 0..MAX+1 { cum[i+1] = cum[i] + dp_v[i]; } let mut dp_r = vec![ModInt(0); MAX+1]; dp_r[0] = ModInt(1); for i in 0..M { for r in (0..MAX+1).rev() { if r >= R[i] { let prev = dp_r[r - R[i]]; dp_r[r] += prev; } } } let mut ans = ModInt(0); for r in 1..MAX+1 { let left = r * A; if left >= MAX { continue; } let right = min(MAX, r * B + 1); ans += dp_r[r] * (cum[right] - cum[left]); } println!("{}", ans); }