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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <string>
#include <functional>
#include <cassert>
#include <cmath>
#define SIZE 600005
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll inv[SIZE],fac[SIZE],finv[SIZE];
void make()
{
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<SIZE;i++)
	{
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		fac[i]=fac[i-1]*(ll) i%MOD;
		finv[i]=finv[i-1]*inv[i]%MOD;
	}
}
ll C(int a,int b)
{
	if(a<b) return 0;
	return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD;
}
ll solve(int n,int m,int L)
{
	ll ret=C(n+L,n);
	//printf("%lld\n",ret);
	for(int t=0;(t+1)*m<=L;t++)
	{
		int zan=L-(t+1)*m;
		int a=n-m,b=m;
		for(int k=0;k*t<=L&&k<=a;k++)
		{
			if(zan<0) break;
			ll vl=C(zan+n,n)*C(a,k)%MOD*C(n,a)%MOD;
			if(k%2==1) ret+=vl;
			else ret+=MOD-vl;
			ret%=MOD;
			zan-=t+1;
		}
		zan=L-(t+2)*m;
		for(int k=0;k*t<=L&&k<=a;k++)
		{
			if(zan<0) break;
			ll vl=C(zan+n,n)*C(a,k)%MOD*C(n,a)%MOD;
			if(k%2==0) ret+=vl;
			else ret+=MOD-vl;
			ret%=MOD;
			zan-=t+1;
		}
	}
	//printf("%d %d %d : %lld\n",n,m,L,ret);
	return ret;
}
int main()
{
	make();
	int n,m,l,r;
	scanf("%d %d %d %d",&n,&m,&l,&r);
	printf("%lld\n",(solve(n,m,r)-solve(n,m,l-1)+MOD)%MOD);
	return 0;
}