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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#define mod 1000000007
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod
#define N 600010
ll fac[N],ivf[N],inv[N];
ll C(ll n,ll k){
    if(n<k)return 0;
    if(k<0)return 0;
    return fac[n]*ivf[n-k]%mod*ivf[k]%mod;
}
ll P(ll n,ll k){
    if(n<k)return 0;
    if(k<0)return 0;
    return fac[n]*ivf[n-k]%mod;
}
ll H(ll n,ll k){
    return C(n+k-1,k);
}

ll beta(ll n,ll m,ll rem,ll upl){
    if(upl==-1){
	return 0;
    }
    ll ans=0;
    for(ll k=0;k*(upl+1)<=rem;k++){
	ll cur=C(n,m)*C(n-m,k)%mod;
	mul(cur,H(n+1,rem-k*(upl+1)));
	if(k%2==0)mad(ans,cur);
	if(k%2==1)mad(ans,-cur);
    }
    //cout<<"#"<<n<<" "<<m<<" "<<rem<<" "<<upl<<" "<<ans<<endl;
    return ans;
}
ll alpha(ll n,ll m,ll sum){//cout<<"---"<<n<<" "<<m<<" "<<sum<<endl;
    ll ans=H(n+1,sum); //cout<<"ans:"<<ans<<endl;
    for(ll x=0;;x++){
	ll rem=sum-(x+1)*m; if(rem<0)break;
	ll cur=beta(n,m,rem,x);
	mad(cur,-beta(n,m,rem,x-1));
	//cout<<x<<" "<<cur<<endl;
	mad(ans,-cur);
    }//cout<<ans<<endl;
    return ans;
}
int main(){
    fac[0]=ivf[0]=inv[1]=1;
    for(int i=1;i<N;i++){
	if(i>1)inv[i]=(mod-(mod/i*inv[mod%i]%mod))%mod;
	fac[i]=fac[i-1]*i%mod;
	ivf[i]=ivf[i-1]*inv[i]%mod;
    }
    
    ll n,m,l,r;
    cin>>n>>m>>l>>r;
    ll ans=alpha(n,m,r)-alpha(n,m,l-1);
    ans%=mod;
    if(ans<0)ans+=mod;
    cout<<ans<<endl;
}