#include #include #include #include #include template inline bool chmin(T &lhs, const U &rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template inline bool chmax(T &lhs, const U &rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } // [l, r) from l to r struct range { struct itr { int i; constexpr itr(int i_): i(i_) { } constexpr void operator ++ () { ++i; } constexpr int operator * () const { return i; } constexpr bool operator != (itr x) const { return i != x.i; } }; const itr l, r; constexpr range(int l_, int r_): l(l_), r(std::max(l_, r_)) { } constexpr itr begin() const { return l; } constexpr itr end() const { return r; } }; // [l, r) from r to l struct revrange { struct itr { int i; constexpr itr(int i_): i(i_) { } constexpr void operator ++ () { --i; } constexpr int operator * () const { return i; } constexpr bool operator != (itr x) const { return i != x.i; } }; const itr l, r; constexpr revrange(int l_, int r_): l(l_ - 1), r(std::max(l_, r_) - 1) { } constexpr itr begin() const { return r; } constexpr itr end() const { return l; } }; template class modulo_int { public: static constexpr int mod = T::value; static_assert(mod > 0, "mod must be positive"); private: long long value; constexpr void normalize() { value %= mod; if (value < 0) value += mod; } public: constexpr modulo_int(long long value_ = 0): value(value_) { normalize(); } constexpr modulo_int operator - () const { return modulo_int(mod - value); } constexpr modulo_int operator ~ () const { return power(mod - 2); } constexpr long long operator () () const { return value; } constexpr modulo_int operator + (const modulo_int &rhs) const { return modulo_int(*this) += rhs; } constexpr modulo_int &operator += (const modulo_int &rhs) { if ((value += rhs.value) >= mod) value -= mod; return (*this); } constexpr modulo_int operator - (const modulo_int &rhs) const { return modulo_int(*this) -= rhs; } constexpr modulo_int &operator -= (const modulo_int &rhs) { if ((value += mod - rhs.value) >= mod) value -= mod; return (*this); } constexpr modulo_int operator * (const modulo_int &rhs) const { return modulo_int(*this) *= rhs; } constexpr modulo_int &operator *= (const modulo_int &rhs) { (value *= rhs.value) %= mod; return (*this); } constexpr modulo_int operator / (const modulo_int &rhs) const { return modulo_int(*this) /= rhs; } constexpr modulo_int &operator /= (const modulo_int &rhs) { return (*this) *= ~rhs; } constexpr bool operator == (const modulo_int &rhs) const { return value == rhs(); } constexpr bool operator != (const modulo_int &rhs) const { return value != rhs(); } constexpr modulo_int power (uint64_t exp) const { modulo_int result(1), mult(*this); while (exp > 0) { if (exp & 1) result *= mult; mult *= mult; exp >>= 1; } return result; } friend std::istream &operator >> (std::istream &stream, modulo_int &lhs) { stream >> lhs.value; lhs.normalize(); return stream; } friend std::ostream &operator << (std::ostream &stream, const modulo_int &rhs) { return stream << rhs.value; } }; using modint = modulo_int>; constexpr int mx = 1000; int main() { int N, M; std::cin >> N >> M; std::vector V(N), R(M); for (int &x: V) { std::cin >> x; } for (int &x: R) { std::cin >> x; } int A, B; std::cin >> A >> B; std::vector vdp(N * mx + 1); vdp.front() = 1; for (int i: range(0, N)) { for (int j: revrange(0, vdp.size())) { if (j -= V[i] >= 0) { vdp[j] += vdp[j - V[i]]; } } } std::vector rdp(M * mx + 1); rdp.front() = 1; for (int i: range(0, M)) { for (int j: revrange(0, rdp.size())) { if (j -= R[i] >= 0) { rdp[j] += rdp[j - R[i]]; } } } std::vector sum(vdp.size() + 1); for (int i: range(0, vdp.size())) { sum[i + 1] += sum[i] + vdp[i]; } modint ans; for (int i: range(0, rdp.size())) { long long ub = std::min((long long) B * i + 1, (long long) vdp.size()); long long lb = std::min((long long) A * i, (long long) vdp.size()); ans += (sum[ub] - sum[lb]) * rdp[i]; } std::cout << ans - 1 << '\n'; return 0; }