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 nn 2024024
#define int long long 
#define mod 1000000007ll
int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=res*x%mod;
		x=x*x%mod;y=y/2;
	}
	return res;
}
int f[nn],rf[nn];
int C(int n,int m){
	if(n<m) return 0;
	return f[n]*rf[m]%mod*rf[n-m]%mod;
}
int n,m,ls,rs;
int dfs(int l,int r,int s){
	if(r*m>s) return 0;
	s-=r*m;int ans=0;l++;
	for(int i=0;i<=n-m and i*l<=s;i++){
		int o=C(n-m,i)*C(s-i*l+n,n)%mod;
		if(i&1) ans-=o;else ans+=o;
		ans%=mod;
	}
	return ans;
}
int calc(int s){
	int ans=0;//return 0;
	for(int x=1;x<=s;x++)
		ans=(ans+dfs(x-1,x,s)-dfs(x-1,x+1,s))%mod;
	return ans;
}
signed main()
{
	f[0]=1;for(int i=1;i<nn;i++) f[i]=f[i-1]*i%mod;
	rf[nn-1]=qpow(f[nn-1],mod-2);
	for(int i=nn-2;i>=0;i--) rf[i]=rf[i+1]*(i+1)%mod;
	cin>>n>>m>>ls>>rs;
	cout<<(C(rs+n,n)-C(ls-1+n,n)-C(n,m)*(calc(rs)-calc(ls-1))%mod+mod*10ll)%mod;
	return 0;
}