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<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXN=600005;
const int mod=1e9+7;
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void dl(int &x,int y){x-=y;if(x<0)x+=mod;}
int pow_mod(int a,int b)
{
	int ret=1;
	for(;b;b>>=1,a=1LL*a*a%mod)if(b&1)ret=1LL*ret*a%mod;
	return ret;
}
int pre[MAXN],inv[MAXN];
int C(int n,int m){return 1LL*pre[n]*inv[m]%mod*inv[n-m]%mod;}
int n,m,L,R;
int query(int p,int q,int lim)//>=p <q
{
	int fx=m,fy=n-m,ret=0;if(1LL*fx*p>lim)return 0;
	for(int i=0;i<=fy;i++)
	{
		int total=lim-i*q-fx*p;
		if(total<0)break;
		int num=1LL*C(total+n,n)*C(n,fx)%mod*C(n-fx,i)%mod;
		if(i&1)dl(ret,num);else ad(ret,num);
	}return ret;
}
int solve(int lim)
{
	int ans=0;
	for(int i=1;i<=lim;i++)ad(ans,query(i,i,lim)),dl(ans,query(i+1,i,lim));
	return (C(lim+n,n)-ans+mod)%mod;
}
int main()
{
	pre[0]=1;for(int i=1;i<MAXN;i++)pre[i]=1LL*pre[i-1]*i%mod;
	inv[MAXN-1]=pow_mod(pre[MAXN-1],mod-2);
	for(int i=MAXN-2;i>=0;i--)inv[i]=1LL*inv[i+1]*(i+1)%mod;
	n=read();m=read();L=read();R=read();
	pr2((solve(R)-solve(L-1)+mod)%mod);
	return 0;
}