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 ll long long
#define uint unsigned
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
using namespace std;
const int mo=1000000007;
const int N=1000005;
int fac[N],inv[N];
int n,m,L,R;
void init(){
	fac[0]=inv[0]=inv[1]=1;
	For(i,2,N-1) inv[i]=1ll*inv[mo%i]*(mo-mo/i)%mo;
	For(i,1,N-1) inv[i]=1ll*inv[i-1]*inv[i]%mo;
	For(i,1,N-1) fac[i]=1ll*fac[i-1]*i%mo;
}
int C(int x,int y){
	if (x<0||y<0||y>x) return 0;
	return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo;
}
int Func(int x,int y){
	return C(x+y-1,y-1);
}
int solve(int V,int mx,int cnt){
	if (mx<0) return 0;
	int ans=0;
	For(i,0,min(cnt,V/(mx+1))){
		int val=(i&1?mo-C(cnt,i):C(cnt,i));
		val=1ll*val*Func(V-i*(mx+1),n+1)%mo;
		ans=(ans+val)%mo;
	}
	return ans;
}
int solve(int V){
	if (V<0) return 0;
	int sum=Func(V,n+1);
	For(vm,0,(V/m)-1){
		int val=solve(V-(vm+1)*m,vm,n-m);
		val=(val+mo-solve(V-(vm+1)*m,vm-1,n-m))%mo;
		sum=(sum+mo-1ll*val*C(n,m)%mo)%mo;
	}
	//printf("%d %d\n",V,sum);
	return sum;
}
int main(){
	init();
	scanf("%d%d%d%d",&n,&m,&L,&R);
	printf("%d\n",(solve(R)+mo-solve(L-1))%mo);
}