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 int long long
const int mod=1e9+7,N=6e5+5;
int ksm(int b,int n){
	int res=1;
	while(n){
		if(n&1) res=res*b%mod;
		b=b*b%mod; n>>=1;
	}
	return res;
}
int fac[N],inv[N];
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=fac[i-1]*i%mod;
	inv[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=0;--i)
		inv[i]=(i+1)*inv[i+1]%mod;
}
int C(int n,int m){
	if(n<m) return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int n,m;
int calc(int S,int x){
	if(S<0) return 0;
	long long res=0,tmp;
	for(int i=0,T=0;i<=n-m && T<=S;++i,T+=x){
		tmp=C(n-m,i)*C(S-T+n,n)%mod;
		if(i&1) res=(res+mod-tmp)%mod;
		else res=(res+tmp)%mod;
	}
	return res*C(n,m)%mod;
}
int solve(int S){
	int res=0;
	for(int x=1;x<=S;++x)
		res+=calc(S-m*x,x)-calc(S-m*(x+1),x),
		res=(res+mod)%mod;
	int ans=C(S+n,n);
	ans=(ans-res+mod)%mod;
	return ans;
}
signed main(){
	cin>>n>>m;
	init(6e5);
	int L,R;
	cin>>L>>R;
	int ans=solve(R)-solve(L-1);
	ans=(ans+mod)%mod;
	cout<<ans;
	return 0;
}