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 rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;

const int N=1000005,mod=1e9+7;
int fac[N],rev[N],n,m,L,R;

int power(int x,int p){
	int res=1;
	for(;p;p>>=1,x=(ll)x*x%mod)
		if(p&1)res=(ll)res*x%mod;
	return res;
}

void init(int n){
	fac[0]=1;
	rep(i,1,n) fac[i]=(ll)fac[i-1]*i%mod;
	rev[n]=power(fac[n],mod-2);
	per(i,n,1) rev[i-1]=(ll)rev[i]*i%mod;
}

int C(int n,int m){
	return m<0||m>n?0:(ll)fac[n]*rev[m]%mod*rev[n-m]%mod;
}
int S(int n,int m){
	return C(n+1,m+1);
}

int solve(int s){
	int res=0;
	rep(x,1,s/m){
		int rem=s-x*m,now=0;
		rep(j,0,min(rem/x,n-m))
			if(j%2==0) now=(now+(ll)S(rem-j*x-1,n-1)*C(n-m,j))%mod;
			else now=(now+mod-(ll)S(rem-j*x-1,n-1)*C(n-m,j)%mod)%mod;
		res=(res+now)%mod;
		if(x==1) continue;
		now=0;
		rep(j,0,min(rem/(x-1),n-m))
			if(j%2==0) now=(now+(ll)S(rem-j*(x-1)-1,n-1)*C(n-m,j))%mod;
			else now=(now+mod-(ll)S(rem-j*(x-1)-1,n-1)*C(n-m,j)%mod)%mod;
		res=(res+mod-now)%mod;
	}
	return (S(s-1,n-1)+mod-(ll)res*C(n,m)%mod)%mod;
}

int main(){
	cin>>n>>m>>L>>R;
	init(N-5);
	cout<<(solve(R+n)+mod-solve(L-1+n))%mod<<endl;
	return 0;
}