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<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 600060
const int mod=1e9+7; 
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,m,L,R,A,B; 
int fac[N],inv[N];
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=1LL*fac[i-1]*i%mod;
	}
	inv[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i){
		inv[i]=1LL*inv[i+1]*(i+1)%mod;
	}
}
inline int C(int n,int m){
	return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int calc(int x,int p,int q){
	if(1LL*(p+1)*m>x)return 0;
	x-=(p+1)*m;
	int ans=0;
	for(int i=0;i<=n-m&&x>=0;++i){
		ans=(ans+1LL*(i&1?-1:1)*C(n-m,i)*C(x+n,n))%mod;
		x-=q+1;
	}
	return (ans+mod)%mod;
}
int Solve(int x){
	int tot=0;
	for(int i=0;i<=x;++i){
		tot=(tot+1LL*(calc(x,i,i)-calc(x,i,i-1)+mod)*C(n,m)%mod)%mod;
	}
	return (C(n+x,n)-tot+mod)%mod;
}
int main(){
	n=read(),m=read(),L=read(),R=read();
	init(n+R);
	printf("%d\n",(Solve(R)-Solve(L-1)+mod)%mod);
	return 0;
}