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 int long long
const int N = 6e5;
const int mod = 1e9+7;
int n,m,inv[600100],p[600100];
inline int pw(int x,int p){
	int res=1;
	while(p){
	  if(p&1)res=res*x%mod;
	  x=x*x%mod;
	  p>>=1;
	}
	return res;
}
inline int c(int nn,int mm){
	if(nn<mm)return 0;
	return p[nn]*inv[mm]%mod*inv[nn-mm]%mod;
}
inline int work(int r){
	int i,j,k,res=0;
	for(k=1;k<=r;k++){
	  for(i=0;i<=m;i++){
	  	if(r-(n-m+i)*k<0)break;
	  	if(i&1)res=(res+c(m,i)*c(r-(n-m+i)*k+n,n)%mod)%mod;
	  	  else res=(res-c(m,i)*c(r-(n-m+i)*k+n,n)%mod+mod)%mod;
	  }
	  for(i=0;i<=m;i++){
	  	if(r-(n-m)*(k+1)-k*i<0)break;
	  	if(i&1)res=(res-c(m,i)*c(r-(n-m)*(k+1)-k*i+n,n)%mod+mod)%mod;
	  	  else res=(res+c(m,i)*c(r-(n-m)*(k+1)-k*i+n,n)%mod)%mod;
	  }
	}
	res=res*c(n,m)%mod;
	res=(res+c(n+r,n))%mod;
	return res;
}
signed main(){
	int i,j,k,l,r;
	scanf("%lld%lld%lld%lld",&n,&m,&l,&r);
	m=n-m;
	p[0]=1;
	for(i=1;i<=N;i++)p[i]=p[i-1]*i%mod;
	inv[N]=pw(p[N],mod-2);
	for(i=N-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
	printf("%lld\n",(work(r)-work(l-1)+mod)%mod);
	return 0;
}