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 rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<int32_t mod>
struct ModInt{
	int32_t a;
	inline int32_t normalize(int64_t x){
		x%=mod;
		if(x<0)x+=mod;
		return x;
	}
	ModInt(const int64_t a=0):a(normalize(a)){}

	ModInt& operator+=(const ModInt &x){
		a+=x.a;
		if(a>=mod)a-=mod;
		return *this;
	}
	ModInt& operator-=(const ModInt &x){
		a-=x.a;
		if(a<0)a+=mod;
		return *this;
	}
	ModInt& operator*=(const ModInt &x){
		a=(int64_t)a*x.a%mod;
		return *this;
	}
	ModInt& operator/=(const ModInt &x){
		*this*=x.inv();
		return *this;
	}

	ModInt operator+(const ModInt x){return ModInt(*this)+=x;}
	ModInt operator-(const ModInt x){return ModInt(*this)-=x;}
	ModInt operator*(const ModInt x){return ModInt(*this)*=x;}
	ModInt operator/(const ModInt x){return ModInt(*this)/=x;}
	bool operator==(const ModInt x){return a==x.a;}
	bool operator!=(const ModInt x){return a!=x.a;}

	ModInt operator-(){return ModInt(0)-ModInt(*this);}
	ModInt pow(int64_t ex)const{
		int64_t x=a;
		int64_t res=1;
		while(ex){
			if(ex&1)res=res*x%mod;
			x=x*x%mod;
			ex>>=1;
		}
		return ModInt(res);
	}
	ModInt inv()const{return pow(mod-2);}
};

template<int32_t mod>
istream& operator>>(istream& in,ModInt<mod>& a){
	return (in>>a.a);
}
template<int32_t mod>
ostream& operator<<(ostream& out,const ModInt<mod>& a){
	return (out<<a.a);
}
using mint=ModInt<1000000007>;

const int LIM=1000000;
mint fact[LIM];
mint inv[LIM];

mint C(int n,int k){
	if(n<0||k<0||n<k)return 0;
	return fact[n]*inv[k]*inv[n-k];
}

mint solve(int N,int M,int R){
	mint ans=0;
	for(int x=1;x<=R;x++){
		for(int k=0;x*k<=R;k++){
			mint tmp=C(N-M,k)*C(R-x*(M+k)+N,N);
			if(k&1)tmp*=-1;
			ans+=tmp;

			tmp=C(N-M,k)*C(R-x*(M+k)-M+N,N);
			if(k%2==0)tmp*=-1;
			ans+=tmp;
		}
	}
	ans*=C(N,M);
	ans=C(R+N,N)-ans;
	return ans;
}

signed main(){
	fact[0]=1;
	for(int i=1;i<LIM;i++)fact[i]=fact[i-1]*i;
	inv[LIM-1]=fact[LIM-1].inv();
	for(int i=LIM-2;i>=0;i--)inv[i]=inv[i+1]*(i+1);

	int N,M,L,R;
	cin>>N>>M>>L>>R;
	L--;

	cout<<(solve(N,M,R)-solve(N,M,L))<<endl;
	return 0;
}