#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC push_options #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #include #include #include using namespace::std; __attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout< #include #include #include // #include // #include // namespace mp = boost::multiprecision; // typedef mp::number> cdouble; // typedef mp::cpp_int cint; templateusing pbds=__gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; templateusing pbds_map=__gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; templateusing hash_map=__gnu_pbds::gp_hash_table; templateusing pqueue =__gnu_pbds::priority_queue,__gnu_pbds::rc_binomial_heap_tag>; typedef long long lint; #define INF (1LL<<60) #define IINF (1<<30) #define EPS (1e-10) #define endl ('\n') #define MOD 1000000007LL //#define MOD 998244353LL typedef vector vec; typedef vector> mat; typedef vector>> mat3; typedef vector svec; typedef vector> smat; templateinline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void numout2(T t){for(auto i:t)numout(i);} templateinline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void output2(T t){for(auto i:t)output(i);} templateinline void _output(T t){bool f=0;for(lint i=0;iinline void _output2(T t){for(lint i=0;i=0;--i) #define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i) #define irep(i) for(lint i=0;;++i) #define all(n) begin(n),end(n) #define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2)) inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;} inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;} // inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;} // inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;} bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;} bool chmax(auto& s,const auto& t){bool res=s dx={1,0,-1,0,1,1,-1,-1}; const vector dy={0,1,0,-1,1,-1,1,-1}; #define SUM(v) accumulate(all(v),0LL) auto call=[](auto f,auto... args){return f(f,args...);}; template struct FPS_BASE:vector{ using vector::vector; inline P operator +(T x)noexcept{return P(*static_cast(this))+=x;} inline P operator -(T x)noexcept{return P(*static_cast(this))-=x;} inline P operator *(T x)noexcept{return P(*static_cast(this))*=x;} inline P operator /(T x)noexcept{return P(*static_cast(this))/=x;} inline P operator <<(int x)noexcept{return P(*static_cast(this))<<=x;} inline P operator >>(int x)noexcept{return P(*static_cast(this))>>=x;} inline P operator +(const P& x)noexcept{return P(*static_cast(this))+=x;} inline P operator -(const P& x)noexcept{return P(*static_cast(this))-=x;} inline P operator -()noexcept{return P(1,T(0))-=P(*static_cast(this));} inline P operator *(const P& x)noexcept{return P(*static_cast(this))*=x;} inline P operator /(const P& x)noexcept{return P(*static_cast(this))/=x;} inline P operator %(const P& x)noexcept{return P(*static_cast(this))%=x;} inline P &operator +=(T x){ if(this->size()==0)this->resize(1,T(0)); (*static_cast(this))[0]+=x; return (*static_cast(this)); } inline P &operator -=(T x){ if(this->size()==0)this->resize(1,T(0)); (*static_cast(this))[0]-=x; return (*static_cast(this)); } inline P &operator *=(T x){ for(int i=0;i<(int)this->size();++i){ (*static_cast(this))[i]*=x; } return (*static_cast(this)); } inline P &operator /=(T x){ return (*static_cast(this))*=(T(1)/x); } inline P &operator <<=(int x){ P ret(x,T(0)); ret.insert(ret.end(),begin(*static_cast(this)),end(*static_cast(this))); return (*static_cast(this))=ret; } inline P &operator >>=(int x){ P ret; ret.insert(ret.end(),begin(*static_cast(this))+x,end(*static_cast(this))); return (*static_cast(this))=ret; } inline P &operator +=(const P& x){ if(this->size()resize(x.size(),T(0)); for(int i=0;i<(int)x.size();++i){ (*this)[i]+=x[i]; } return (*static_cast(this)); } inline P &operator -=(const P& x){ if(this->size()resize(x.size(),T(0)); for(int i=0;i<(int)x.size();++i){ (*static_cast(this))[i]-=x[i]; } return (*static_cast(this)); } inline P &operator *=(const P& x){ return (*static_cast(this))=mul((*static_cast(this)),x); } inline P &operator /=(P x){ if(this->size()clear(); return (*static_cast(this)); } const int n=this->size()-x.size()+1; return (*static_cast(this)) = (rev().pre(n)*x.rev().inv(n)).pre(n).rev(n); } inline P &operator %=(const P& x){ return ((*static_cast(this))-=*static_cast(this)/x*x); } inline P& shrink(){while((*static_cast(this)).back()==0)(*static_cast(this)).pop_back();return (*static_cast(this));} inline P pre(int sz)const{ return P(begin(*this),begin(*this)+min((int)this->size(),sz)); } inline P rev(int deg=-1){ P ret(*static_cast(this)); if(deg!=-1)ret.resize(deg,T(0)); reverse(begin(ret),end(ret)); return ret; } P inv(int deg=-1){ assert((*static_cast(this))[0]!=T(0)); const int n=deg==-1?this->size():deg; P ret({T(1)/(*this)[0]}); for(int i=1;i(this)); for(int i=0;isize(),x.size()));++i){ ret[i]*=x[i]; } return ret; } P diff(){ P ret(*static_cast(this)); for(int i=0;i<(int)ret.size();i++){ ret[i]*=i; } return ret>>1; } P integral(){ P ret(*static_cast(this)); for(int i=0;i<(int)ret.size();i++){ ret[i]/=i+1; } return ret<<1; } P log(int deg=-1){ assert((*this)[0]==T(1)); const int n=deg==-1?this->size():deg; return (diff()*inv(n)).pre(n-1).integral(); } P exp(int deg=-1){ assert((*this)[0]==T(0)); const int n=deg==-1?this->size():deg; P ret({T(1)}); for(int i=1;isize():deg; if((*this)[0]==T(0)) { for(int i=1;i<(int)this->size();i++) { if((*this)[i]!=T(0)) { if(i&1)return{}; if(n-i/2<=0)break; auto ret=(*this>>i).sqrt(n-i/2)<<(i/2); if((int)ret.size()size()-1;i>=0;--i){ res*=x; res+=(*this)[i]; } return res; } vector multipoint_eval(const vector&x){ const int n=x.size(); P* v=new P[2*n-1]; for(int i=0;i=0;i--){v[i]=v[i*2+1]*v[i*2+2];} v[0]=P(*static_cast(this))%v[0];v[0].shrink(); for(int i=1;ires(n); for(int i=0;i struct fps1:FPS_BASE>{ class mint_fps; using FPS_BASE>::FPS_BASE; using P=fps1; P mul(P s,P t)override{ lint n=s.size()+t.size()-1; lint h=1; while((1<a(1< ntt(vector v,const int& h,const bool& inv){ int n=v.size(),mask=n-1; vector tmp(n); vector table(n,1); mint_fps theta=mint_fps(3).base(h); if(inv)theta=theta.inv(); for(int i=1;i>1,t=h-1;j>=1;j>>=1,--t){ for(int k=0;k>t; tmp[k]=v[((i<<(t+1))|s)&mask]+table[i*j]*v[((i<<(t+1))|j|s)&mask]; } swap(v,tmp); } if(inv)for(int i=0;i=0?x%get_mod():get_mod()-(-x)%get_mod(); } } constexpr u64 value() noexcept { return garner(); } constexpr mint_fps operator+(const mint_fps rhs)const noexcept{return mint_fps(*this) += rhs;} constexpr mint_fps operator-(const mint_fps rhs)const noexcept{return mint_fps(*this)-=rhs;} constexpr mint_fps operator*(const mint_fps rhs) const noexcept {return mint_fps(*this) *= rhs;} constexpr mint_fps operator/(const mint_fps rhs) const noexcept {return mint_fps(*this) /= rhs;} constexpr mint_fps &operator+=(const mint_fps rhs) noexcept { for(int i=0;i<3;++i){ a[i]+=rhs.a[i]; if (a[i]>=mods[i])a[i]-=mods[i]; } return *this; } constexpr bool operator==(mint_fps x) noexcept { return a==x.a; } constexpr bool operator!=(mint_fps x) noexcept { return a!=x.a; } constexpr mint_fps &operator-=(const mint_fps rhs) noexcept { for(int i=0;i<3;++i){ a[i]-=rhs.a[i]; if (a[i]>=mods[i])a[i]-=mods[i]; } return *this; } constexpr mint_fps &operator*=(const mint_fps rhs) noexcept { for(int i=0;i<3;++i){ a[i]=a[i]*rhs.a[i]%mods[i]; } return *this; } constexpr mint_fps &operator/=(mint_fps rhs)noexcept{ for(int i=0;i<3;i++){ u64 ret =rhs.a[i]; u64 exp=mods[i]-2; while (exp) { if (exp %2) { (a[i]*=ret)%=mods[i]; } (ret *= ret)%=mods[i]; exp /= 2; } } return *this; } constexpr mint_fps operator++(int n) noexcept { return *this+=1; } constexpr mint_fps operator--(int n) noexcept { return *this-=1; } constexpr mint_fps base(int h)noexcept{ for(int i=0;i<3;i++){ u64 ret =3; a[i]=1; u64 exp=((mods[i]-1)>>h); while (exp) { if (exp %2) { (a[i]*=ret)%=mods[i]; } (ret *= ret)%=mods[i]; exp /= 2; } } return *this; } constexpr mint_fps inv(){ return mint_fps(1)/(*this); } constexpr static u64 get_mod(){return MOD;} constexpr u64 garner(){ const int sz=3; using u64 = long long; const u64 mods[4]={1224736769,1045430273,1007681537,get_mod()}; u64 coeffs[sz+1]={1,1,1,1}; u64 constants[sz+1]={}; auto modinv=[](u64 x,u64 mod){ u64 y=mod-2; u64 ret=1; while(y>0) { if(y&1)(ret*=x)%=mod; (x*=x)%=mod; y>>=1; } return ret; }; for(int i=0;i=0?x%get_mod():get_mod()-(-x)%get_mod()){} constexpr u64 &value()noexcept{return a;} constexpr const u64 &value() const noexcept {return a;} constexpr mint operator+(const mint rhs)const noexcept{return mint(*this) += rhs;} constexpr mint operator-(const mint rhs)const noexcept{return mint(*this)-=rhs;} constexpr mint operator*(const mint rhs) const noexcept {return mint(*this) *= rhs;} constexpr mint operator/(const mint rhs) const noexcept {return mint(*this) /= rhs;} constexpr mint &operator+=(const mint rhs) noexcept { a += rhs.a; if (a >= get_mod())a -= get_mod(); return *this; } constexpr mint &operator-=(const mint rhs) noexcept { if (a= get_mod())a -= get_mod(); return *this; } constexpr mint operator--(int n) noexcept { if (a<1)a += get_mod(); a -= 1; return *this; } constexpr mint &operator/=(mint rhs) noexcept { u64 exp=get_mod()-2; while (exp) { if (exp % 2) { *this *= rhs; } rhs *= rhs; exp /= 2; } return *this; } constexpr bool operator==(mint x) noexcept { return a==x.a; } constexpr bool operator!=(mint x) noexcept { return a!=x.a; } constexpr static int root(){ mint root = 2; while(root.pow((get_mod()-1)>>1).a==1)root++; return root.a; } constexpr mint pow(long long n){ long long x=a; mint ret = 1; while(n>0) { if(n&1)(ret*=x); (x*=x)%=get_mod(); n>>=1; } return ret; } constexpr mint inv(){ return pow(get_mod()-2); } static vector fac,ifac; static bool init; void build(){ init=0; fac.resize(10101011); ifac.resize(10101011); fac[0]=1,ifac[0]=1; for(int i=1;i<10101011;i++)fac[i]=fac[i-1]*i; ifac[10101010]=fac[10101010].inv(); for(int i=10101009;i>=0;i--)ifac[i]=ifac[i+1]*(i+1); } mint comb(lint b){ if(init)build(); if(a==0&&b==0)return 1; if((lint)a>(istream& lhs,mint& rhs) noexcept { lhs >> rhs.a; return lhs; } constexpr static u64 get_mod(){return MOD;} }; vector mint::fac; vector mint::ifac; bool mint::init=1; int main(){ lint n,m; cin>>n>>m; vectorv(n),r(m); rep(i,n)cin>>v[i]; rep(i,m)cin>>r[i]; lint A,B; cin>>A>>B; lint sv=SUM(v),sr=SUM(r); vector> dp1(n+1,vector(sv+1,0)),dp2(m+1,vector(m*sr+1,0)); dp1[0][0]=1;dp2[0][0]=1; repi(i,1,n+1)rep(j,sv+1){ dp1[i][j]=dp1[i-1][j]+(j-v[i-1]>=0?dp1[i-1][j-v[i-1]]:0); } repi(i,1,m+1)rep(j,sr+1){ dp2[i][j]=dp2[i-1][j]+(j-r[i-1]>=0?dp2[i-1][j-r[i-1]]:0); } vectorb(sv+2,0); rep(i,sv+1)b[i+1]=b[i]+dp1[n][i]; mint ans=0; repi(i,1,sr+1){ mint tmp=(i*B+1>=sv+2?b.back():b[i*B+1])-(i*A>=sv+2?b.back():b[i*A]); ans+=tmp*dp2[m][i]; } cout<