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 ll long long
#define maxn 600100
#define base 1000000007

using namespace std;

int n,m,l,r;
ll fac[maxn],finv[maxn],inv[maxn],ans;

void init() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for (int i=2;i<maxn;i++) {
        inv[i] = base - inv[base%i]*(base/i)%base;
        fac[i] = (1ll*fac[i-1]*i)%base;
        finv[i] = (finv[i-1]*inv[i])%base;
    }
}

ll C(int k,int n) {
    if (n<k||k<0) return 0;
    return fac[n]*finv[k]%base*finv[n-k]%base;
}

ll solve2(int R1,int n,int m,int x) {
    ll tmp=0;
    if (R1<0) return 0;
    for (int k=0;k<=n-m&&k*x<=R1;k++) {
        int R2 = R1-k*x;
        ll ea = C(k,n-m) * C(R2,R2+n)%base;
        if (k%2==0) tmp = (tmp+ea)%base;
        else tmp = (tmp-ea+base)%base;
    }
    return tmp;
}

ll solve(int R,int n,int m) {
    ll tmp = C(R,R+n);
    for (int x=1;m*x<=R;x++) tmp = (tmp - C(m,n)*(solve2(R-x*m,n,m,x) - solve2(R-(x+1)*m,n,m,x)+base)%base + base)%base;
    return tmp;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin);
    cin>>n>>m>>l>>r;
    init();
    ans = (solve(r,n,m) - solve(l-1,n,m) + base)%base;
    cout << ans;
}