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 clr(x) memset(x,0,sizeof(x))
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define kill _z_kill
#define y0 _z_y0
#define y1 _z_y1
#define x0 _z_x0
#define x1 _z_x1
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double LD;
typedef vector <int> vi;
typedef pair <int,int> pii;
void enable_comma(){}
string tostring(char c);
string tostring(LL x);
template <class A,class B> string tostring(pair <A,B> p);
template <class A> string tostring(vector <A> v);
string tostring(char c){
	string s="";
	s+=c;
	return s;
}
string tostring(string s){
	return "\""+s+"\"";
}
string tostring(char *c){
	return tostring((string)c);
}
string tostring(LL x){
	if (x<0)
		return "-"+tostring(-x);
	if (x>9)
		return tostring(x/10)+tostring(char('0'+x%10));
	else
		return tostring(char('0'+x));
}
string tostring(int x){
	return tostring((LL)x);
}
string tostring(ull x){
	if (x>9)
		return tostring((LL)(x/10))+tostring(char('0'+x%10));
	else
		return tostring(char('0'+x));
}
string tostring(uint x){
	return tostring((LL)x);
}
string tostring(double x){
	static char res[114];
	sprintf(res,"%lf\n",x);
	return tostring(res);
}
string tostring(LD x){
	return tostring((double)x);
}
template <class A,class B> string tostring(pair <A,B> p){
	return "("+tostring(p.fi)+","+tostring(p.se)+")";
}

template <class A> string tostring(vector <A> v){
	string res="{";
	For(i,0,(int)v.size()-1){
		res+=tostring(v[i]);
		res+=i==(int)v.size()-1?"}":",";
	}
	if (res=="{")
		res+="}";
	return res;
}
template <class A> string tostring(A a,int L,int R){
	string res="{";
	For(i,L,R){
		res+=tostring(a[i]);
		res+=i==R?"}":",";
	}
	if (res=="{")
		res+="}";
	return res;
}
string tostrings(){
	return "";
}
template <typename Head,typename... Tail>
string tostrings(Head H,Tail... T){
	return tostring(H)+" "+tostrings(T...);
}
#define User_Time ((double)clock()/CLOCKS_PER_SEC)
#ifdef zzd
	#define outval(x) cerr<<#x" = "<<tostring(x)<<endl
	#define outvals(...) cerr<<"["<<#__VA_ARGS__<<"]: "<<tostrings(__VA_ARGS__)<<endl
	#define outtag(x) cerr<<"--------------"#x"---------------"<<endl
	#define outsign(x) cerr<<"<"#x">"<<endl
	#define outarr(a,L,R) cerr<<#a"["<<(L)<<".."<<(R)<<"] = "<<tostring(a,L,R)<<endl
#else
	#define outval(x) enable_comma()
	#define outvals(...) enable_comma()
	#define outtag(x) enable_comma()
	#define outsign(x) enable_comma()
	#define outarr(a,L,R) enable_comma()
#endif
#ifdef ONLINE_JUDGE
	#ifdef assert
		#undef assert
	#endif
	#define assert(x) (!(x)?\
			cout<<"Assertion failed!"<<endl<<\
			"function: "<<__FUNCTION__<<endl<<\
			"line: "<<__LINE__<<endl<<\
			"expression: "<<#x<<endl,exit(3),0:1)
#endif
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
template <class T> void ckmax(T &x,const T y){
	if (x<y)
		x=y;
}
template <class T> void ckmin(T &x,const T y){
	if (x>y)
		x=y;
}
const int mod=1e9+7;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
int md(LL x){
	return (x%mod+mod)%mod;
}
const int N=600006;
int fac[N],ifac[N],inv[N];
void prework(){
	int n=N-1;
	fac[0]=1;
	For(i,1,n)
		fac[i]=(LL)fac[i-1]*i%mod;
	ifac[n]=Pow(fac[n],mod-2);
	Fod(i,n,1)
		ifac[i-1]=(LL)ifac[i]*i%mod;
	inv[1]=1;
	For(i,2,n)
		inv[i]=(LL)(mod-mod/i)*inv[mod%i]%mod;
}
int C(LL n,int m){
	if (m<0||m>n)
		return 0;
	return (LL)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int solve(int n,int m,int k){
	m=n-m;
	int ans=0;
	For(i,0,k)
		For(j,0,k/(i+1))
			ans=md(ans+(LL)C(n,m)*C(m,j)%mod*C(k-(LL)((n-m)+j)*(i+1)+n,n)*(j&1?-1:1));
	For(i,0,k)
		For(j,0,k/(i+1))
			ans=md(ans-(LL)C(n,m)*C(m,j)%mod*C(k-(LL)(n-m)*(i+2)-(LL)j*(i+1)+n,n)%mod*(j&1?-1:1));
	return Del(C(k+n,n)-ans);
}
int main(){
	prework();
	int n=read(),m=read(),L=read(),R=read();
	cout<<Del(solve(n,m,R)-solve(n,m,L-1))<<endl;
	return 0;
}