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<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=600000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 1000000007
#define eps 1e-8
int n,m,l,r;
ll fac[N+10],invfac[N+10];

int read()
{
    int x=0,f=1;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;
}

ll qpow(ll x,int y)
{
	ll ans=1;
	while (y)
	{
		if (y&1) ans=ans*x%maxd;
		x=x*x%maxd;y>>=1;
	}
	return ans;
}

void init()
{
	fac[0]=invfac[0]=1;
	rep(i,1,N) fac[i]=fac[i-1]*i%maxd;
	invfac[N]=qpow(fac[N],maxd-2);
	per(i,N-1,1) invfac[i]=invfac[i+1]*(i+1)%maxd;
}

ll C(int n,int m)
{
	if ((n<m) || (n<0) || (m<0)) return 0;
	return fac[n]*invfac[m]%maxd*invfac[n-m]%maxd;
}

ll calc(int n,int m,int sum,int lim,int r)
{
	if (sum<1ll*m*r) return 0;
	sum-=m*r;
	ll ans=0;
	for (int i=0,f=1;i<=n-m;i++,f*=-1)
	{
		ll tmp=C(n-m,i)*C(n+sum,n)%maxd;
		ans=(ans+tmp*f+maxd)%maxd;
		sum-=lim;
		if (sum<0) break;
	}
	return ans*C(n,m)%maxd;
}

ll solve(int n,int m,int sum)
{
	ll ans=C(n+sum,n);
	per(i,sum,1)
	{
		ll del=(calc(n,m,sum,i,i)-calc(n,m,sum,i,i+1)+maxd)%maxd;
		ans=(ans-del+maxd)%maxd;
	}
	return ans;
}

int main()
{
	init();
	n=read();m=read();l=read();r=read();
	printf("%lld",(solve(n,m,r)-solve(n,m,l-1)+maxd)%maxd);
	return 0;
}