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:
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll MOD=(ll)1e9+7;
const int N=1e6;

ll fac[N],invfac[N+3];

ll QPow(ll Ca,ll Cb){
	ll ret=1;
	while(Cb){
		if(Cb&1) ret=ret*Ca%MOD;
		Ca=Ca*Ca%MOD;
		Cb>>=1;
	}
	return ret;
}
ll funC(int Ca,int Cb){return fac[Cb]*invfac[Ca]%MOD*invfac[Cb-Ca]%MOD;}
//sum( A[1~n] ) + B = S, A[1~m] >= Vr , 0 <= A[m+1,n] < Vl
ll funF(int n,int m,ll S,ll Vl,ll Vr){
	if(S-m*Vr<0) return 0;
	else S-=m*Vr;
	ll ret=0;
	for(int i=0,tmp=1;i<=n-m && Vl*i<=S;i++,tmp*=-1)
		ret=(ret+MOD+tmp*funC(i,n-m)*funC(n,S-i*Vl+n)%MOD)%MOD;
	return ret*funC(m,n)%MOD;
}
ll Solve(int n,int m,int S){
	ll ret=funC(n,S+n);
	for(int i=S;i>=1;i--)
		ret=(ret+MOD-(funF(n,m,S,i,i)+MOD-funF(n,m,S,i,i+1))%MOD)%MOD;
	return ret;
}
int main(){
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%MOD;
	invfac[N-1]=QPow(fac[N-1],MOD-2);
	for(int i=N-2;i>=0;i--) invfac[i]=invfac[i+1]*(i+1)%MOD;
	int n,m,Sl,Sr;
	scanf("%d%d%d%d",&n,&m,&Sl,&Sr);
	printf("%lld\n",(Solve(n,m,Sr)+MOD-Solve(n,m,Sl-1))%MOD);
	return 0;
}