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 <iostream>

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define inver(a) power(a, mod - 2)

using namespace std;

inline char nc()
{
//	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
	x=0; int f=1,ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x*=f;
}

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 6e5 + 50;
int N, M, L, R;

int fac[maxn];
int inv[maxn];
ll power(ll x, ll y)
{
	ll re = 1;
	while(y) 
	{
		if(y & 1) re = re * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return re;
}
void binom_init(int n)
{
	fac[0] = 1;
	for(int i = 1; i <= n; ++i)
	{
		fac[i] = (ll)fac[i - 1] * i % mod;
	} 
	inv[n] = inver(fac[n]);
	for(int i = n; i >= 1; --i)
	{
		inv[i - 1] = (ll)inv[i] * i % mod;
	}
}
int binom(int x,int y)
{
	return (ll)fac[x] * inv[y] % mod * inv[x - y] % mod;
}

int cal(int a, int b, int K)
{
	if(K < (ll)a * M) return 0;
	int an = 0;
	K -= a * M;
	for(int i = 0; i <= N - M && K >= 0; ++i)
	{
		int f = i & 1 ? -1 : 1;
		an = (an + (ll)binom(K + N, N) * binom(N - M, i) * f) % mod;
		K -= b + 1;
	}
	an = (ll)an * binom(N, M) % mod;
	return an;
}
int sol(int K)
{
	int an = 0;
	for(int x = 1; x <= K; ++x)
	{
		an = ((ll)an + cal(x, x - 1, K) - cal(x + 1, x - 1, K)) % mod;
	}
	an = (binom(K + N, N) - an) % mod;
	return an;
}

int main()
{
	read(N), read(M), read(L), read(R);
	binom_init(R + N);
	int an = (sol(R) - sol(L - 1)) % mod;
	an = (an + mod) % mod;
	printf("%d\n", an);
	return 0;
}