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<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#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--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 766666, mo = 1e9+7, inv2 =(mo+1)/2;
int n,m,fac[N],ifac[N];
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
inline int power(int a, int n) {
	int res=1;
	while (n) {
		if (n&1) res=1LL*res*a%mo;
		a=1LL*a*a%mo; n>>=1;
	}
	return res;
}
int C(int n, int m){
	assert(n<N);
	return m>=0&&m<=n?1LL*fac[n]*ifac[m]%mo*ifac[n-m]%mo:0;
}
void init(int n){
	fac[0]=1;rep(i,1,n)fac[i]=1LL*fac[i-1]*i%mo;
	ifac[n]=power(fac[n],mo-2);per(i,n-1,0)ifac[i]=1LL*ifac[i+1]*(i+1)%mo;
}
int calc(int r){
	int res=0;
	rep(i,0,r)if(1LL*(1+i)*(n-m)<=r){
	//	cerr<<i<<endl;
		int lim=r-(1+i)*(n-m);
		for(int j=0;j<=m&&lim-(i+1)*j>=0;j++)
			res=(res+1LL*C(m,j)*(j&1?mo-1:1)%mo*C(n+lim-(i+1)*j,n))%mo;
		if(i){
		for(int j=0;j<=m&&lim-(i)*j>=0;j++)
			res=((res-1LL*C(m,j)*(j&1?mo-1:1)%mo*C(n+lim-(i)*j,n))%mo+mo)%mo;
		}
	}
	return ((C(r+n,n)-1LL*C(n,m)*res)%mo+mo)%mo;
}
int main() {
	init(N-1);read(n);read(m);m=n-m;int l,r;read(l);read(r);
//	cerr<<(calc(r))<<' '<<(calc(l-1)+mo)%mo<<endl;
	cout<<(calc(r)-calc(l-1)+mo)%mo;
	return 0;
}