// I SELL YOU...! #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using P = pair; using TP = tuple; void init_io(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } #define MOD 1000000007 #define MAX 5050000 ll vsum[MAX][2]={},rsum[MAX][2]={}; void solve_dp(ll dp[MAX][2],vector &v,ll n){ dp[0][0] = 1; for(int i=0;i=v[i]){ dp[j][1] += dp[j-v[i]][0]; dp[j][1] %= MOD; } } for(int j=0;j> n >> m; vector v(n),r(m); vector sum(MAX+1,0); for(int i=0;i> v[i]; } for(int i=0;i> r[i]; } solve_dp(vsum,v,n); solve_dp(rsum,r,m); for(int i=0;i> a >> b; for(int i=1;i=MAX) break; ans = (ans+(sum[r+1]-sum[l])*rsum[i][0]+MOD)%MOD; } cout << ans << endl; }