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>

using namespace std;


#ifdef zxc

#include <sys/resource.h>
#include "debug.h"

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = int64_t;
using ld = long double;
const ld EPS = 1e-9;
//const ll MOD = 924844033;
const ld PI = 3.141592653589793;
const int maxn = 600001;
const ll MOD = 1e9 + 7;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}


ll add(ll a, ll b) {
    a += b;
    if (a >= MOD) {
        a -= MOD;
    }
    return a;
}

ll mul(ll a, ll b) {
    return a * b % MOD;
}

ll pw(ll a, ll b) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
    }
    return res;
}

ll fac[maxn];
ll inv[maxn];

void precalc(int n) {
    fac[0] = 1;
    for (int i = 1; i < n; ++i) {
        fac[i] = mul(fac[i - 1], i);
    }
    inv[n - 1] = pw(fac[n - 1], MOD - 2);
    for (int i = n - 2; i >= 0; --i) {
        inv[i] = mul(inv[i + 1], i + 1);
    }
}

ll C(ll n, ll k) {
    if (k < 0 || k > n) {
        return 0;
    }
    return fac[n] * inv[n - k] % MOD * inv[k] % MOD;
}

inline ll distribute(ll n, ll sum) {
    return C(sum + n, n);
}

signed main() {
#ifdef zxc
    struct rlimit rl;
    const rlim_t kStackSize = 512L * 1024L * 1024L;
    assert(!getrlimit(RLIMIT_STACK, &rl));
    rl.rlim_cur = kStackSize;
    assert(!setrlimit(RLIMIT_STACK, &rl));
    freopen("../input.txt", "r", stdin);
//    freopen("../kolya_output.txt", "w", stdout);
#else
    //    mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    //            freopen("", "r", stdin);
    //        freopen("hack.out", "w", stdout);
#endif

    auto count_bad_sequences = [](ll n, ll m, ll sum, ll x, ll y) { // m elements >=x
        // n-m elements <=y
        ll choose_big = C(n, m);
        sum -= x * m;
        ll res = mul(choose_big, distribute(n, sum));

        for (int i = 1; i <= n - m && i * (y + 1) <= sum; ++i) {
            ll choose_small = C(n - m, i);
            ll val = choose_big * choose_small % MOD * distribute(n, sum - (y + 1) * i) % MOD;
            if (i & 1) {
                res = add(res, MOD - val);
            } else {
                res = add(res, val);
            }
        }
//        debug(n, m, sum, x, y, res);
        return res;
    };
    auto count_good_sequences = [&](ll n, ll m, ll sum) {
        ll res = distribute(n, sum);
        for (int k = 1; k <= sum; ++k) {
            ll cur = add(count_bad_sequences(n, m, sum, k, k - 1), MOD - count_bad_sequences(n, m, sum, k + 1, k - 1));
            res = add(res, MOD - cur);
        }
        return res;
    };
    auto solve = [&](int _) {
        int n, m, l, r;
        cin >> n >> m >> l >> r;
        ll ans = add(count_good_sequences(n, m, r), MOD - count_good_sequences(n, m, l - 1));
        cout << ans;
    };
    precalc(maxn);

    fast_io();
    cout.precision(9);
    cout << fixed;
    auto start = chrono::steady_clock::now();

    for (int i = 1; i <= 1; ++i) solve(i);
    auto end = chrono::steady_clock::now();

    debug("time", chrono::duration_cast<chrono::milliseconds>(end - start).count() / 1000.0);

}