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>
using namespace std;
const int N=600005;
const int MOD=1000000007;
int n,m,L,R;
long long fac[N],inv[N];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
void init(int n=600000)
{
	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;i>=1;i--)
		inv[i-1]=inv[i]*i%MOD;
	return;
}
long long C(int n,int m)
{
	if(m>n) return 0;
	else return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
long long calc(long long x,int p,int q)
{
	x-=1LL*m*p;
	if(x<0) return 0;
	long long res=0;
	for(int i=0;i<=n-m&&x-1LL*i*q>=0;i++)
		if(i&1) res=(res-C(n-m,i)*C(x-1LL*i*q+n,n)%MOD+MOD)%MOD;
		else res=(res+C(n-m,i)*C(x-1LL*i*q+n,n)%MOD)%MOD;
	res*=C(n,m);
	return res;
}
long long solve(int x)
{
	long long res=0;
	for(int p=1;p<=x;p++)
		res=(res+(calc(x,p,p)-calc(x,p+1,p)+MOD)%MOD)%MOD;
	res=(C(x+n,n)-res+MOD)%MOD;
	return res;
}
int main()
{
	init();
	scanf("%d%d%d%d",&n,&m,&L,&R);
	printf("%lld",(solve(R)-solve(L-1)+MOD)%MOD);
	return 0;
}