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 MOD 1000000007
template<typename ty1,typename ty2>
inline int add(ty1 x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x += y; return x < MOD ? x : x - MOD;
}
template<typename ty1,typename ty2>
inline void addto(ty1 &x, ty2 y) {
		  if(y>=MOD)y%=MOD;
		  if(x>=MOD)x%=MOD;
	      x += y; if (x >= MOD) x -= MOD;
}
template<typename ty1,typename ty2>
inline int sub(ty1 x, ty2 y) {
		if(y>=MOD)y%=MOD;
		 if(x>=MOD)x%=MOD;
        x -= y; return x < 0 ? x + MOD : x;
}
template<typename ty1,typename ty2>
inline void subto(ty1 &x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x -= y; if (x < 0) x += MOD;
}
template<typename ty1,typename ty2>
inline int mul(ty1 x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        return 1ll * x * y % MOD;
}
template<typename ty1,typename ty2>
void multo(ty1 &x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        x=1ll * x * y % MOD;
}

#define MOD 1000000007
class Combination{
	long long int ppow(long long int i, long long int j){
		long long int res = 1LL;
		while (j){
			if ((j & 1LL)){
				res *= i;
				if (res >= MOD){
					res %= MOD;
				}
			}
			j >>= 1;
			i *= i;
			if (i >= MOD){
				i %= MOD;
			}
		}
		return res;
	}
public:
	vector<long long int> k;
	vector<long long int> r;
	void resize(int N){
		k.resize(N + 2);
		r.resize(N + 2);
		k[0] = 1;
		for (int i = 1; i < N+2; i++){
			k[i] = k[i - 1];
			k[i] *= i;
			if (k[i] >= MOD)k[i] %= MOD;
		}
		long long int al = k[k.size() - 1];
		long long int iv = ppow(k[k.size() - 1],MOD-2);
		r[k.size() - 1] = iv;
		for (int i = (int)(r.size()) - 2; i >= 0; i--){
			r[i] = r[i + 1] * (i + 1);
			if (r[i] >= MOD){
				r[i] %= MOD;
			}
		}
	}
	long long int C(int a, int b){
		if (a < b)return 0;
		long long int up = k[a];
		long long int dw = r[b] * r[a - b];
		dw %= MOD;
		up *= dw;
		up %= MOD;
		return up;
	}
	long long int H(int a, int b){
		return C(a + b - 1, b);
	}
	long long int catalan_number(int n){
		return (C(2 * n, n) + MOD - C(2 * n, n - 1)) % MOD;
	}
};
Combination C;

#define MAX 300002

int n;
int m;
int l;
int r;

long long int distribute(long long int val){  //n個にval以下をdistribute
	if(val<0)return 0;
	//ダミー
	int nd=n+1;
	return C.C(val+nd-1,val);
}
long long int w1[1000002];
long long int w2[1000002];

//vector<int> v[100002];


long long int gt(long long int cnt, int cnt2,long long int val1,long long int val2){  //cnt個がval1以上でi個以上がval2以上
	if(cnt>n)return 0;
	int way1=C.C(n,cnt);  //val以上の選び方
	int way2=C.C(n-cnt,cnt2);
	long long int lef=l-1-val1*cnt-(val2+1)*cnt2;
	long long int rig=r-val1*cnt-(val2+1)*cnt2;
	int ds=sub(distribute(rig),distribute(lef));
	return mul(way2,mul(ds,way1));
}
map<pair<int,pair<long long int,long long int> >,vector<int> > mp;
long long int gt2(long long int cnt,long long int val1,long long int val2){  //cnt個の値がval1以上でn-cnt個がval2以下
	if(cnt>n)return 0;
	//if(mp.count(make_pair(cnt,make_pair(val1,val2)))return mp[make_pair(val1,val2)]
	//auto &v=mp[make_pair(val1,val2)];
	long long int tmp=0;
	long long int z=r-val1*cnt;
	z/=(val2+1);
	for(int i=z;i>=0;i--){
		long long int u=gt(cnt,i,val1,val2);
		tmp=sub(u,tmp);
	}
	return tmp;
}
long long int cn2(int cnt,int val){  //cnt個の値がval1以上でかつ最小値はval1
	int way1=sub(gt2(cnt,val,val-1),gt2(cnt,val+1,val-1));
	return way1;
}
long long int cn(int cnt ,int val){
	return cn2(cnt,val);//sub(cn2(cnt,val),cn2(cnt+1,val));
}
int main(){
	cin>>n>>m>>l>>r;
	int ans=0;
	C.resize(1000000);
	/*for(int i=1;i<=r;i++){
		int cn=r/i;
		v[i].push_back(0);
		for(int j=1;j<=cn;j++){
			v[i].push_back(gt(j,i));
		}
		long long int cur=0;
		long long int ti=0;
		for(int j=v[i].size()-1;j>=0;j--){
			long long int tmp=v[i][j];
			v[i][j]=sub(v[i][j],cur);
			cur=sub(tmp,cur);
			subto(v[i][j],ti);
			addto(ti,v[i][j]);
		}
	}*/
	for(int i=1;i<=r;i++){
		//i
		//cerr<<i<<" "<<cn(m,i)<<endl;
		addto(ans,cn(m,i));
	}
	int overall=sub(distribute(r),distribute(l-1));
	//cerr<<overall<<endl;
	subto(overall,ans);
	printf("%d\n",overall);
	return 0;
}