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;
typedef long long ll;
const int max_n=600005;
const int mod=1e9+7;
inline int Add(int x,int y){
    return (x+=y)>=mod?x-mod:x;
}
inline int Sub(int x,int y){
    return (x-=y)<0?x+mod:x;
}
inline int Mul(int x,int y){
    return 1ll*x*y%mod;
}
inline int Pow(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=1ll*res*x%mod;
        y>>=1;
        x=1ll*x*x%mod;
    }
    return res;
}
int m,n,l,r;
int f[max_n],inv[max_n];
void init(int n){
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=1ll*f[i-1]*i%mod;
    inv[n]=Pow(f[n],mod-2);
    for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int C(int n,int m){
    if(n<m||m<0)return 0;
    return 1ll*f[n]*inv[m]%mod*inv[n-m]%mod;
}
int cal(int a,int b,int s){
    int res=0;
    for(int i=0;i<=n-m;i++){
        int ts=s-m*a-i*(b+1);
        if(ts<0)break;
        if(i&1)res=Sub(res,Mul(C(n-m,i),C(ts+n,n)));
        else res=Add(res,Mul(C(n-m,i),C(ts+n,n)));
    }
    res=Mul(res,C(n,m));
    //cout<<res<<endl;
    return res;
}
int solve(int s){
    int res=C(s+n,n);
    //cout<<res<<endl;
    for(int x=1;x*m<=s;x++){
        res=Sub(res,Sub(cal(x,x-1,s),cal(x+1,x-1,s)));
       // cout<<x<<' '<<cal(x,x-1,s)<<' '<<cal(x+1,x-1,s)<<endl;
    }
    return res;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&l,&r);
    init(max_n-1);
    int ans=(solve(r)-solve(l-1)+mod)%mod;
    printf("%d\n",ans);
    return 0;
}