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 rep(i,n) for (int i = 0; i < (int)n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

ll kai[1000001];
ll mokai[1000001];

ll mod_pow (ll x, ll y) {
    ll ret = 1;
    while (y) {
        if (y&1) ret = ret*x%MOD;
        x = x*x%MOD;
        y /= 2;
    }
    return ret;
}

void init (int _n) {
    kai[0] = 1;
    for (int i = 1; i <= _n; i++) kai[i] = kai[i-1]*i%MOD;
    for (int i = 0; i <= _n; i++) mokai[i] = mod_pow(kai[i],MOD-2);
}

ll conb (ll x, ll y) {
    ll z = x-y;
    if (z < 0) return 0;
    ll ret = kai[x]*mokai[y]%MOD;
    ret = ret*mokai[z]%MOD;
    return ret;
}

ll N, M, L, R;

ll core (ll x, ll z, ll T) {
    if (x*M > T) return 0;
    ll ret = 0;
    for (ll i = 0; i <= N-M; i++) {
        ll tmp = ((i%2?-1:1)*conb(N-M, i)+MOD)%MOD;
        ll t = T - x*M + N - i*z;
        if (t < N) break;
        tmp = tmp * conb(t, N) % MOD;
        ret = (ret + tmp) % MOD;
    }
    ret = ret * conb(N,M) % MOD;
    return ret;
}

ll solve (ll T) {
    ll ret = 0;
    for (ll i = 1; ; i++) {
        if (M*i > T) break;
        ret = (ret + core(i, i, T) - core(i+1, i, T) + MOD) % MOD;
    }
    ret = (conb(T+N,N) - ret + MOD) % MOD;
    return ret;
}

int main() {
    cin >> N >> M >> L >> R;
    init(1000000);
    cout << (solve(R) - solve(L-1) + MOD) % MOD << endl;
}