// #define _GLIBCXX_DEBUG // for STL debug (optional) #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 using namespace std; using ll = long long int; using int64 = long long int; template void chmax(T &a, T b) {a = max(a, b);} template void chmin(T &a, T b) {a = min(a, b);} template void chadd(T &a, T b) {a = a + b;} int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const int INF = 1LL << 29; const ll LONGINF = 1LL << 60; const ll MOD = 1000000007LL; // ModInt begin using ll = long long; template struct ModInt { ll v; ll mod_pow(ll x, ll n) const { return (!n) ? 1 : (mod_pow((x*x)%mod,n/2) * ((n&1)?x:1)) % mod; } ModInt(ll a = 0) : v((a %= mod) < 0 ? a + mod : a) {} ModInt operator+ ( const ModInt& b ) const { return (v + b.v >= mod ? ModInt(v + b.v - mod) : ModInt(v + b.v)); } ModInt operator- () const { return ModInt(-v); } ModInt operator- ( const ModInt& b ) const { return (v - b.v < 0 ? ModInt(v - b.v + mod) : ModInt(v - b.v)); } ModInt operator* ( const ModInt& b ) const {return (v * b.v) % mod;} ModInt operator/ ( const ModInt& b ) const {return (v * mod_pow(b.v, mod-2)) % mod;} bool operator== ( const ModInt &b ) const {return v == b.v;} bool operator!= ( const ModInt &b ) const {return !(*this == b); } ModInt& operator+= ( const ModInt &b ) { v += b.v; if(v >= mod) v -= mod; return *this; } ModInt& operator-= ( const ModInt &b ) { v -= b.v; if(v < 0) v += mod; return *this; } ModInt& operator*= ( const ModInt &b ) { (v *= b.v) %= mod; return *this; } ModInt& operator/= ( const ModInt &b ) { (v *= mod_pow(b.v, mod-2)) %= mod; return *this; } ModInt pow(ll x) { return ModInt(mod_pow(v, x)); } // operator int() const { return int(v); } // operator long long int() const { return v; } }; template ModInt pow(ModInt n, ll k) { return ModInt(n.mod_pow(n.v, k)); } template ostream& operator<< (ostream& out, ModInt a) {return out << a.v;} template istream& operator>> (istream& in, ModInt& a) { in >> a.v; return in; } // ModInt end using mint = ModInt; mint dp1[1000010], dp2[1000010]; int main() { int N, M; scanf("%d%d", &N, &M); vector V(N), R(M); for(int i=0; i=0; j--) { if(dp1[j] == mint(0)) continue; int nj = min(MAXP, j + B*R[i]); dp1[nj] += dp1[j]; } } for(int i=0; i= 0) dp1[nj] += dp1[j]; } } for(int i=0; i<=MAXP; i++) { if(dp1[i] == mint(0)) continue; ans += dp1[i]; } } { dp2[0] = mint(1); for(int i=0; i=0; j--) { if(dp2[j] == mint(0)) continue; int nj = min(MAXP, j + A*R[i]); dp2[nj] += dp2[j]; } } for(int i=0; i= 0) dp2[nj] += dp2[j]; } } for(int i=1; i<=MAXP; i++) { if(dp2[i] == mint(0)) continue; ans -= dp2[i]; } } cout << ans << endl; return 0; }