Problem: Problem statement

N-winged rabbit is on a balance beam of length L-1. The initial position of the i-th rabbit is the integer x_i, which satisfies 0 ≤ x_ {i} \ lt x_ {i + 1} ≤ L−1. The coordinates increase as you move to the right. Any i-th rabbit can jump to the right (ie, move from x_i to x_i + a_i) any number of times, just a distance a_i. However, you cannot jump over another rabbit or enter a position below -1 or above L. Also, at most one rabbit can jump at the same time, and at most one rabbit can exist at a certain coordinate.

How many possible states of x_ {0},…, x_ {N−1} after starting from the initial state and repeating the jump any number of times? Find by the remainder divided by 1 \, 000 \, 000 \, 007.

input

The input is given in the following format.


N L
x_ {0}… x_ {N−1}
a_ {0}… a_ {N−1}


Constraint

* All inputs are integers
* 1 \ ≤ N \ ≤ 5 \,000
* N \ ≤ L \ ≤ 5 \,000
* 0 \ ≤ x_ {i} \ lt x_ {i + 1} \ ≤ L−1
* 0 \ ≤ a_ {i} \ ≤ L−1



output

Print the answer in one line.

sample

Sample input 1


13
0
1


Sample output 1


3


If 1/0 is used to express the presence / absence of a rabbit, there are three ways: 100, 010, and 001.

Sample input 2


twenty four
0 1
1 2


Sample output 2


Four


There are four ways: 1100, 1001, 0101, 0011.

Sample input 3


10 50
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1


Sample output 3


272278100


The binomial coefficient C (50,10) = 10 \, 272 \, 278 \, 170, and the remainder obtained by dividing it by 1 \, 000 \, 000 \, 007 is 272 \, 278 \, 100.





Example

Input

1 3
0
1


Output

3

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <bitset>

using namespace std;

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
template <typename T> void print_container(ostream& os, const T& c) { const char* _s = " "; if (!c.empty()) { __typeof__(c.begin()) last = --c.end(); foreach (it, c) { os << *it; if (it != last) os << _s; } } }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const set<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const multiset<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const deque<T>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }

template <typename T> void print(T a, int n, const string& split = " ") { for (int i = 0; i < n; i++) { cout << a[i]; if (i + 1 != n) cout << split; } cout << endl; }
template <typename T> void print2d(T a, int w, int h, int width = -1, int br = 0) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }
template <typename T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
#define dump(v) (cerr << #v << ": " << v << endl)

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define erep(i, n) for (int i = 0; i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define clr(a, x) memset(a, x, sizeof(a))
#define sz(a) ((int)(a).size())
#define mp(a, b) make_pair(a, b)
#define ten(n) ((long long)(1e##n))

template <typename T, typename U> void upmin(T& a, const U& b) { a = min<T>(a, b); }
template <typename T, typename U> void upmax(T& a, const U& b) { a = max<T>(a, b); }
template <typename T> void uniq(T& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }
void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }
bool in_rect(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }

typedef long long ll;
typedef pair<int, int> pint;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };


int main()
{
    int n, l;
    cin >> n >> l;

    vector<int> x(n), a(n);
    input(x, n);
    input(a, n);

    const int mod = ten(9) + 7;
    static int dp[5555][5555];
    dp[n][l] = 1;
    for (int i = n - 1; i >= 0; --i)
    {
        int ways = 0;
        for (int p = l; p >= x[i]; --p)
        {
            if (a[i] == 0 && p == x[i] || a[i] != 0 && (p - x[i]) % a[i] == 0)
                dp[i][p] = ways;

            (ways += dp[i + 1][p]) %= mod;
        }
    }

    int res = 0;
    rep(p, l)
        (res += dp[0][p]) %= mod;
    cout << res << endl;
}