#define _CRT_SECURE_NO_WARNINGS #pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i, n) for(int i=0;i<(int)(n);i++) #define REP(i, n) for(int i=1;i<=(int)(n);i++) #define all(V) V.begin(),V.end() typedef long long lint; typedef std::pair P; constexpr int INF = INT_MAX / 10; constexpr lint LINF = LLONG_MAX / 2; constexpr double eps = 1e-9; template class prique :public std::priority_queue, std::greater> {}; template> class Vector { using traits = std::allocator_traits; public: using value_type = T; using allocator_type = Alloc; using size_type = unsigned int; using difference_type = int; using reference = T&; using const_reference = const T&; using pointer = typename traits::pointer; using const_pointer = typename traits::const_pointer; class iterator { public: using difference_type = int; using value_type = Vector::value_type; using pointer = Vector::pointer; using reference = Vector::reference; using iterator_category = std::random_access_iterator_tag; private: pointer p; public: iterator()noexcept :p() {} iterator(const Vector& base, difference_type index) noexcept :p(base.e + index) {} iterator(const iterator& i) :p(i.p) {} iterator& operator=(const iterator& i) = default; iterator& operator=(iterator&& i)noexcept = default; iterator& operator++() { p++; return *this; } iterator operator++(int) { iterator res = *this; p++; return res; } iterator operator+(const difference_type& x)const { iterator res = *this; return res += x; } iterator& operator+=(const difference_type& x) { p += x; return *this; } iterator& operator--() { p--; return *this; } iterator operator--(int) { iterator res = *this; p--; return res; } iterator operator-(const difference_type x)const { iterator res = *this; return res -= x; } difference_type operator-(const iterator& i)const { return p - i.p; } iterator& operator-=(const difference_type x) { p -= x; return *this; } reference operator*()const { return *p; } reference operator[](const difference_type x)const { return *(p + x); } bool operator<(const iterator& i)const { return p < i.p; } bool operator<=(const iterator& i)const { return p <= i.p; } bool operator==(const iterator& i)const { return p == i.p; } bool operator>(const iterator& i)const { return p > i.p; } bool operator>=(const iterator& i)const { return p >= i.p; } bool operator!=(const iterator& i)const { return p != i.p; } }; class const_iterator { public: using difference_type = int; using value_type = Vector::value_type; using pointer = const Vector::pointer; using reference = const Vector::reference; using iterator_category = std::random_access_iterator_tag; private: pointer p; public: const_iterator()noexcept :p() {} const_iterator(const Vector& base, difference_type index) noexcept :p(base.e + index) {} const_iterator(const const_iterator& i) :p(i.p) {} const_iterator& operator=(const const_iterator& i)noexcept = default; const_iterator& operator=(const_iterator&& i)noexcept = default; const_iterator& operator++() { p++; return *this; } const_iterator operator++(int) { const_iterator res = *this; p++; return res; } const_iterator operator+(const difference_type x)const { const_iterator res = *this; return res += x; } const_iterator& operator+=(const difference_type x) { p += x; return *this; } const_iterator& operator--() { p--; return *this; } const_iterator operator--(int) { const_iterator res = *this; p--; return res; } const_iterator operator-(const difference_type x)const { const_iterator res = *this; return res -= x; } difference_type operator-(const const_iterator& i)const { return p - i.p; } const_iterator& operator-=(const difference_type x) { p -= x; return *this; } reference operator*()const { return *p; } reference operator[](const difference_type x)const { return *(p + x); } bool operator<(const const_iterator& i)const { return p < i.p; } bool operator<=(const const_iterator& i)const { return p <= i.p; } bool operator==(const const_iterator& i)const { return p == i.p; } bool operator>(const const_iterator& i)const { return p > i.p; } bool operator>=(const const_iterator& i)const { return p >= i.p; } bool operator!=(const const_iterator& i)const { return p != i.p; } }; using reverse_iterator = std::reverse_iterator; using const_reverse_iterator = std::reverse_iterator; private: pointer e; size_type length = 0, cap = 1; Alloc alloc; static_assert(std::is_same::value, "The allocator value type is not matched the Vector value type."); static_assert(!std::is_const::value, "This library forbids containers of const elements"); public: Vector() :Vector(Alloc()) {} explicit Vector(const Alloc& a)noexcept :alloc(a) { e = alloc.allocate(cap); } explicit Vector(size_type n, const Alloc& a = Alloc()) :alloc(a) { while (cap < n)cap *= 2; e = alloc.allocate(cap); rep(i, n)emplace_back(); } explicit Vector(size_type n, const_reference value, const Alloc& a = Alloc()) :alloc(a) { while (cap < n)cap *= 2; e = alloc.allocate(cap); rep(i, n)emplace_back(value); } template Vector(InputIter first, InputIter last, const Alloc& a = Alloc()) :alloc(a) { e = alloc.allocate(cap); for (InputIter i = first; i != last; i++) { emplace_back(*i); } } Vector(const Vector& x, const Alloc& a = Alloc()) :alloc(a) { while (cap < x.length)cap *= 2; length = x.length; e = alloc.allocate(cap); rep(i, x.length)traits::construct(alloc, e + i, *(x.e + i)); } Vector(Vector&& x, const Alloc& a = Alloc()) :alloc(a) { cap = x.cap; length = x.length; e = x.e; x.e = nullptr; } ~Vector() { if (e != nullptr) { rep(i, length)traits::destroy(alloc, e + i); alloc.deallocate(e, cap); } } Vector& operator=(const Vector& x) { rep(i, length)traits::destroy(alloc, e + i); alloc.deallocate(e, cap); length = x.length; cap = 1; while (cap < length)cap *= 2; e = alloc.allocate(cap); rep(i, length)traits::construct(alloc, e + i, *(x.e + i)); return *this; } Vector& operator=(Vector&& x) { rep(i, length)traits::destroy(alloc, e + i); alloc.deallocate(e, cap); cap = x.cap; length = x.length; e = x.e; x.e = nullptr; return *this; } private: void extension() { pointer e_ = alloc.allocate(cap * 2); rep(i, length)traits::construct(alloc, e_ + i, *(e + i)); rep(i, length)traits::destroy(alloc, e + i); alloc.deallocate(e, cap); e = e_; cap *= 2; } void extension(size_type n) { unsigned int r = 1; while (cap * r < n)r *= 2; if (r == 1)return; pointer e_ = alloc.allocate(cap * r); rep(i, length)traits::construct(alloc, e_ + i, *(e + i)); rep(i, length)traits::destroy(alloc, e + i); alloc.deallocate(e, cap); e = e_; cap *= r; } public: template void assign(InputIter first, InputIter last) { size_type cnt = 0; for (InputIter i = first; i != last; i++) { if (cnt == cap) { length = std::max(length, cnt); extension(); } traits::construct(alloc, e + cnt, *i); cnt++; } } void assign(size_type n, const_reference value) { extension(n); std::fill(e, e + n, value); } template void emplace_back(Args&&... args) { if (length == cap)extension(); traits::construct(alloc, e + length, std::forward(args)...); length++; } void push_back(const_reference value) { emplace_back(value); } void push_back(T&& value) { emplace_back(std::move(value)); } void pop_back() { traits::destroy(alloc, e + length); length--; } void reserve(size_type n) { extension(n); } iterator erase(iterator pos) { const iterator res = pos; iterator t = pos; t++; for (iterator i = pos; t != end(); i++, t++) { *i = std::move(*t); } pop_back(); return res; } iterator erase(iterator first, iterator last) { const iterator res = first; typename iterator::difference_type d = last - first; for (iterator i = first; i + d != end(); i++) { *i = std::move(*(i + d)); } rep(i, d)pop_back(); return res; } void swap(Vector& x) { std::swap(length, x.length); std::swap(cap, x.cap); std::swap(e, x.e); } void clear() { while (length)pop_back(); } size_type size()const { return length; } void resize(size_type n, const_reference value = T()) { extension(n); while (n < length)pop_back(); length = n; std::fill(e, e + n, value); } size_type capacity()const { return cap; } bool empty()const { return !length; } reference operator[](const size_type pos)const { return e[pos]; } pointer data() { return e; } reference front() { return *e; } reference back() { return *(e + length - 1); } iterator begin() noexcept { return iterator(*this, 0); } const_iterator begin()const noexcept { return const_iterator(*this, 0); } const_iterator cbegin()const noexcept { return const_iterator(*this, 0); } iterator rbegin()noexcept { return reverse_iterator(*this, 0); } const_iterator rbegin()const noexcept { return const_reverse_iterator(*this, 0); } const_iterator crbegin()const noexcept { return const_reverse_iterator(*this, 0); } iterator end() noexcept { return iterator(*this, length); } const_iterator end()const noexcept { return const_iterator(*this, length); } const_iterator cend()const noexcept { return const_iterator(*this, length); } iterator rend()noexcept { return reverse_iterator(*this, length); } const_iterator rend()const noexcept { return const_reverse_iterator(*this, length); } const_iterator crend()const noexcept { return const_reverse_iterator(*this, length); } }; template inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; } template inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; } inline lint gcd(lint a, lint b) { while (b) { lint c = a; a = b; b = c % b; } return a; } inline lint lcm(lint a, lint b) { return a / gcd(a, b) * b; } bool isprime(lint n) { if (n == 1)return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0)return false; } return true; } lint mypow(lint a, lint b) { if (!b)return 1; if (b & 1)return mypow(a, b - 1) * a; lint memo = mypow(a, b >> 1); return memo * memo; } lint modpow(lint a, lint b, lint m) { if (!b)return 1; if (b & 1)return modpow(a, b - 1, m) * a % m; lint memo = modpow(a, b >> 1, m); return memo * memo % m; } template void printArray(std::vector& vec) { rep(i, vec.size() - 1)std::cout << vec[i] << " "; std::cout << vec.back() << std::endl; } template void printArray(Vector& vec) { rep(i, vec.size() - 1)std::cout << vec[i] << " "; std::cout << vec.back() << std::endl; } template void printArray(T l, T r) { T rprev = r; rprev--; for (T i = l; i != rprev; i++) { std::cout << *i << " "; } std::cout << *rprev << std::endl; } std::string to_string(Vector& vec) { std::string res = "["; rep(i, vec.size() - 1)res += std::to_string(vec[i]) + ", "; res += std::to_string(vec.back()) + "]"; return res; } template class ModInt { lint value; public: ModInt() : value(0) {} template ModInt(T value = 0) : value(value) { if (value < 0)value = -(lint)(-value % modulo) + modulo; this->value = value % modulo; } inline operator int()const { return value; } inline ModInt& operator+=(const ModInt& x) { value += x.value; if (value >= modulo)value -= modulo; return *this; } inline ModInt& operator++() { if (value == modulo - 1)value = 0; else value++; return *this; } inline ModInt operator-()const { return ModInt(0) -= *this; } inline ModInt& operator-=(const ModInt& x) { value -= x.value; if (value < 0)value += modulo; return *this; } inline ModInt& operator--() { if (value == 0)value = modulo - 1; else value--; return *this; } inline ModInt& operator*=(const ModInt& x) { value = value * x.value % modulo; return *this; } inline ModInt& operator/=(ModInt rhs) { int exp = modulo - 2; while (exp) { if (exp & 1)*this *= rhs; rhs *= rhs; exp >>= 1; } return *this; } template ModInt operator+(const T& rhs)const { return ModInt(*this) += rhs; } template ModInt& operator+=(const T& rhs) { return operator+=(ModInt(rhs)); } template ModInt operator-(const T& rhs)const { return ModInt(*this) -= rhs; } template ModInt& operator-=(const T& rhs) { return operator-=(ModInt(rhs)); } template ModInt operator*(const T& rhs)const { return ModInt(*this) *= rhs; } template ModInt& operator*=(const T& rhs) { return operator*=(ModInt(rhs)); } template ModInt operator/(const T& rhs)const { return ModInt(*this) /= rhs; } template ModInt& operator/=(const T& rhs) { return operator/=(ModInt(rhs)); } }; template std::istream& operator>>(std::istream& ist, ModInt& x) { lint a; ist >> a; x = a; return ist; } lint n, m, v[110], r[110], a, b; ModInt<> dp[2][110][100010]; int main() { std::cin >> n >> m; rep(i, n)std::cin >> v[i]; rep(i, m)std::cin >> r[i]; std::cin >> a >> b; dp[0][0][0] = 1; rep(i, n) { rep(j, 100001) { if (j + v[i] <= 100000)dp[0][1][j + v[i]] += dp[0][0][j]; dp[0][1][j] += dp[0][0][j]; } rep(j, 100001) { dp[0][0][j] = dp[0][1][j]; dp[0][1][j] = 0; } } dp[1][0][0] = 1; rep(i, m) { rep(j, 100001) { if (j + r[i] <= 100000)dp[1][1][j + r[i]] += dp[1][0][j]; dp[1][1][j] += dp[1][0][j]; } rep(j, 100001) { dp[1][0][j] = dp[1][1][j]; dp[1][1][j] = 0; } } ModInt<> ans = 0; rep(i, 100000)dp[0][0][i + 1] += dp[0][0][i]; REP(i, 100000) { ans += dp[1][0][i] * (dp[0][0][std::min((lint)100000, i * b)] - dp[0][0][std::min((lint)100000, i * a - 1)]); } std::cout << ans << std::endl; return 0; }