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>
const int mu=  int(1E9) + 7,MOD=1000000007;
const int N=300005;
int n,m,l,r,p[N*2],inv[N*2];
int c(int x,int y){
	if (x<y) return 0;
	return p[x]*1ll*inv[y]%mu*inv[x-y]%mu;
}
int solve2(int n,int m,int s,int x,int y){
	int ans=0;
	if (s-1ll*m*x<0) return 0;
	else s=s-1ll*m*x;
	int f=1;
	for (int i=0,f=1;i<=n-m && s>=0;i++,f=1ll*f*(mu-1)%mu,s=s-y){
		ans=(ans+1ll*f*c(s+n,n)%mu*c(n-m,i)%mu)%mu;
	}
	return 1ll*ans*c(n,m)%mu;
}
int solve(int n,int m,int s){
	int ans=c(s+n,n);
	for (int i=s;i>=1;i--){
		//枚举第m个数 
		int del=(solve2(n,m,s,i,i)+mu-solve2(n,m,s,i+1,i))%mu;
		ans=(ans+mu-del)%mu;//容斥 
	}
	return ans;
}
int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=1ll*x*x%mu) 
		if (y&1) ans=ans*1ll*x%mu;
	return ans;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&l,&r);
	p[0]=1;
	for (int i=1;i<=n+r;i++)p[i]=1ll*p[i-1]*i%mu;
	inv[n+r]=ksm(p[n+r],mu-2);
	for(int i=n+r-1;i>=0;i--) inv[i]=inv[i+1]*1ll*(i+1)%mu; 
	printf("%d\n",(solve(n,m,r)-solve(n,m,l-1)+mu)%mu);
}