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>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long LL;
const LL P = 1e9+7;
const int N = 6e5+5;
 
int fac[N], ifac[N];
int n, m, L, R;

int pw(LL x,int n){
	LL res = 1;
	for(;n;n>>=1,x=x*x%P)if(n&1)res=res*x%P;
	return res;
}
int C(int x,int y){
	if(y<0 || y>x) return 0;
	return 1ll * fac[x] * ifac[y] % P * ifac[x-y] % P;
}
int calc(int n,int sumL,int sumR){
	return (C(sumR+n,n) - C(sumL-1+n,n) + P) % P;
}
 
int main(){
	fac[0] = 1;
	rep(i,1,N-1) fac[i] = 1ll * fac[i-1] * i % P;
	ifac[N-1] = pw(fac[N-1], P-2);
	rrep(i,N-2,0) ifac[i] = 1ll * ifac[i+1] * (i+1) % P;
	
	cin>>n>>m>>L>>R;
	int sall = calc(n,L,R), s1 = 0;
	
	rep(i,1,R){
		int sL = L - m * i, sR = R - m * i, r = i - 1, res = 0;
		if(sR<0) break;
		
		rep(j,0,n-m){
			int sl = sL - j * (r+1), sr = sR - j * (r+1);
			if(sr<0) break;
			res = (res + (j%2==0 ? 1ll : -1ll) * calc(n,sl,sr) * C(n-m, j) % P + P) % P;
		}
		
		sL = L - m * (i+1), sR = R - m * (i+1);
		rep(j,0,n-m){
			int sl = sL - j * (r+1), sr = sR - j * (r+1);
			if(sr<0) break;
			res = (res - (j%2==0 ? 1ll : -1ll) * calc(n,sl,sr) * C(n-m, j) % P + P) % P;
		}
		s1 = (s1 + 1ll * res * C(n, m) % P) % P;
	}
	cout<<(sall - s1 + P) % P <<endl;
	return 0;
}