Problem: Find the number of sequences of N non-negative integers A_1, A_2, ..., A_N that satisfy the following conditions:

* L \leq A_1 + A_2 + ... + A_N \leq R
* When the N elements are sorted in non-increasing order, the M-th and (M+1)-th elements are equal.



Since the answer can be enormous, print it modulo 10^9+7.

Constraints

* All values in input are integers.
* 1 \leq M < N \leq 3 \times 10^5
* 1 \leq L \leq R \leq 3 \times 10^5

Input

Input is given from Standard Input in the following format:


N M L R


Output

Print the number of sequences of N non-negative integers, modulo 10^9+7.

Examples

Input

4 2 3 7


Output

105


Input

2 1 4 8


Output

3


Input

141592 6535 89793 238462


Output

933832916

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define int long long
using ll = long long;
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
#define S set<int>
#define itn int
bool dbg = false;
//Template by yosupo
template <uint MD>
struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(_v % MD + MD); }
    M& set_v(uint _v)
    {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const
    {
        M x = *this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<MOD>;
//Template by yosupo
const int MN = 1000000;
Mint fact[MN], iFac[MN];

void first()
{
    fact[0] = Mint(1);
    for (int i = 1; i < MN; i++)
        fact[i] = fact[i - 1] * Mint(i);
    iFac[MN - 1] = fact[MN - 1].inv();
    for (int i = MN - 1; i >= 1; i--) {
        iFac[i - 1] = iFac[i] * Mint(i);
    }
    assert(fact[2345] * iFac[2345] == Mint(1));
}
Mint C(int n, int k)
{
    if (n < k || k < 0)
        return Mint(0);
    return fact[n] * iFac[k] * iFac[n - k];
}

itn N, M, L, R;

Mint solve2(int r, int n, int k, int x)
{
    Mint ans = 0;
    FORR(l, k, n)
    {
        int r2 = r - l * x;
        if (r2 < 0)
            break;
        Mint buf = C(n, l) * C(r2 + n, n) * C(l, k);
        if ((l + k) % 2)
            ans -= buf;
        else
            ans += buf;
    }
    return ans;
}

Mint solve(int n, int k, int r)
{
    Mint ans = C(r + n, n);
    FORR(x, 0, MN)
    {
        int r2 = r - k * x;
        if (r2 < 0)
            break;
        ans -= solve2(r, n, k, x);
        ans += solve2(r - k, n, k, x);
    }
    return ans;
}

signed main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    first();
    cin >> N >> M >> L >> R;
    Mint ans = 0;
    ans += solve(N, M, R);
    dump(ans);
    ans -= solve(N, M, L - 1);
    cout << ans << endl;
    return 0;
}