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 ci const int&
#define C(x,y) (1ll*fac[x]*invf[y]%mod*invf[x-y]%mod)
using namespace std;
const int mod=1e9+7;
int n,m,l,r,S,fac[600010],invf[600010];
int POW(int x,int y){
	int tot=1;
	while(y)y&1?tot=1ll*tot*x%mod:0,x=1ll*x*x%mod,y>>=1;
	return tot;
}
int Calc(ci s,ci ri,ci li){
	S=s-ri*m;
	if(S<0)return 0;
	int ans=0;
	for(int i=0,op=1;i<=n-m&&S>=0;++i,op=-op,S-=li)ans=(ans+1ll*op*C(S+n,n)*C(n-m,i)%mod+mod)%mod;
	return 1ll*ans*C(n,m)%mod;
}
int Solve(ci s){
	int ans=0;
	for(int i=0;i<=s/m;++i)ans=(ans+1ll*(Calc(s,i,i)-Calc(s,i+1,i)+mod)%mod)%mod;
	return (C(s+n,n)-ans+mod)%mod;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&l,&r),fac[0]=1;
	for(int i=1;i<=n+r;++i)fac[i]=1ll*fac[i-1]*i%mod;
	invf[n+r]=POW(fac[n+r],mod-2);
	for(int i=n+r-1;i>=0;--i)invf[i]=1ll*invf[i+1]*(i+1)%mod;
	printf("%d",(Solve(r)-Solve(l-1)+mod)%mod);
	return 0;
}