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 <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x)
{
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=6e5+10,mod=1e9+7;
inline void Add(int &x,int y) { x+=y; if(x>=mod) x-=mod; }
inline void Dec(int &x,int y) { x-=y; if(x<0) x+=mod; }
int Pow(int x,int y) {
	int res=1;
	while(y) {
		if(y&1) res=res*(ll)x%mod;
		x=x*(ll)x%mod,y>>=1;
	}
	return res;
}
int fac[N],inv[N];
inline void predo(int n) {
	fac[0]=1; for(int i=1;i<=n;++i) fac[i]=fac[i-1]*(ll)i%mod;
	inv[n]=Pow(fac[n],mod-2); for(int i=n;i>=1;--i) inv[i-1]=inv[i]*(ll)i%mod;
}
int C(int n,int m) { return fac[n]*(ll)inv[m]%mod*inv[n-m]%mod; }
int n,m,ans,L,R;
int get(int s) { return C(s+n,n); }
int calc(int s,int a,int b) {
	int ans=0;
	for(int j=0;j<=n-m&&s-a*m-j*(b+1)>=0;++j) {
		int tmp=get(s-a*m-j*(b+1))*(ll)C(n-m,j)%mod;
		if(j&1) Dec(ans,tmp);
		else Add(ans,tmp);
	}
	return ans*(ll)C(n,m)%mod;
}
int sol(int s) {
	int ans=get(s);
	for(int i=1;i*m<=s;++i) {
		Dec(ans,calc(s,i,i-1));
		Add(ans,calc(s,i+1,i-1));
	}
//	cout<<s<<' '<<ans<<endl;
	return ans;
}
int main() {
	predo(6e5);
	rd(n),rd(m),rd(L),rd(R);
	int ans=sol(R)-sol(L-1);
	printf("%d",(ans%mod+mod)%mod);
	return 0;
}