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;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int MOD = 1000 * 1000 * 1000 + 7, N = 1e6 + 7;
int mod(int n) {
    n %= MOD;
    if (n < 0) return n + MOD;
    else return n;
}   
int fp(int a, int p) {
    int ans = 1, c = a;
    for (int i = 0; (1ll << i) <= p; ++i) {
        if ((p >> i) & 1) ans = mod(ans * c);
        c = mod(c * c);
    }   
    return ans;
}   
int dv(int a, int b) { return mod(a * fp(b, MOD - 2)); }

int f[N], inv[N];
int C(int n, int k) {
    return mod(f[n] * mod(inv[k] * inv[n - k]));
}   
int comp(int n, int k) {
    //number of swquences with k elemeths and sum = n

    return C(n + k - 1, k - 1);
}
int get(int sum, int n) {
    //number of sequences with n elemeths and sum <= sum

    if (sum < 0)
        return 0;

    return comp(sum, n + 1);
}   

int n, m;

int get_bad(int l, int r, int R, int bad) {
    int ans = C(n, m);
    ans = mod(ans * C(n - m, bad));
    int have = m * r + bad * (l + 1);
    return mod(ans * get(R - have, n));
}

int cut(int l, int r, int R) {
    // m elemeths >= r, n - m elemenths <= l

    if (l < 0)
        return 0;
    int ans = 0;
    for (int bad = 0; bad <= n - m && bad * (l + 1) + m * r <= R; ++bad) {
        if (bad & 1) {
            ans = mod(ans - get_bad(l, r, R, bad));
        }   
        else {
            ans = mod(ans + get_bad(l, r, R, bad));
        }   
    }   
    return ans;
}   
int solve(int r) {
    int ans = 0;
    for (int i = 0; i < r; ++i) {
        ans += cut(i, i + 1, r) - cut(i - 1, i + 1, r);
    }       
    return ans;
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    f[0] = 1;
    for (int i = 1; i < N; ++i)
        f[i] = mod(f[i - 1] * i);
    inv[N - 1] = fp(f[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; --i)
        inv[i] = mod(inv[i + 1] * (i + 1));

    int l, r;
    cin >> n >> m >> l >> r;
    int bad = mod(solve(r) - solve(l - 1));
    int all = get(r, n) - get(l - 1, n);
    cout << mod(all - bad) << endl;
}