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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

constexpr ll mod=1e9+7;

ll mod_pow(ll a,ll b){
	a%=mod;
	if(b==0)return 1;
	if(b==1)return a;
	ll res=mod_pow(a,b/2)%mod;
	res*=res; res%=mod;
	if(b%2)res*=a;
	return res%mod;
}

struct perm{
private:
	int sz;
	vector<ll> p,invp;
public:
	perm(int n){
		sz=n+1;
		p.resize(sz),invp.resize(sz);
		p[0]=1;
		for(int i=1;i<=sz-1;i++){
			p[i]=p[i-1]*i%mod;
		}
		invp[sz-1]=mod_pow(p[sz-1],mod-2);
		for(int i=sz-2;i>=0;i--){
			invp[i]=invp[i+1]*(i+1)%mod;
		}
	}
	ll comb(ll x,ll y){
		if(x<y||y<0)return 0;
		return (p[x]*invp[x-y]%mod)*invp[y]%mod;
	}
};
perm p(2e6);

ll cul(ll n,ll m,ll r,ll a,ll b){
	ll res=0;
	for(int i=0;i<=n-m;i++){
		ll rr=r-m*a-i*(b+1);
		if(rr<0)break;
		if(i%2==0){
			(res+=p.comb(n+rr,rr)*p.comb(n-m,i)%mod)%=mod;
		}else{
			(res-=p.comb(n+rr,rr)*p.comb(n-m,i)%mod)%=mod;
		}
	}
	return res;
}


ll solve(ll n,ll m,ll r){
	ll res=p.comb(n+r,r);
	ll sum=0;
	for(ll i=1;i<=r;i++){
		if((ll)m*i>r)break;
		(sum+=cul(n,m,r,i,i-1)-cul(n,m,r,i+1,i-1))%=mod;
	}
	(sum*=p.comb(n,m))%=mod;
	(res-=sum)%=mod;
	if(res<0)res+=mod;
	return res;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	ll n,m,l,r; cin >> n >> m >> l >> r;
	ll res=(solve(n,m,r)-solve(n,m,l-1))%mod;
	if(res<0)res+=mod;
	printf("%lld\n",res);
}