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 For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int mod = 1e9+7;
inline int Mod(int x){
	return x>=mod?x-mod:x;
}
inline int power(int a,int b){
	int ret=1;
	for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) ret=1ll*ret*a%mod;
	return ret;
}

const int N = 6e5;
int fac[N+10],ifac[N+10];
inline void init(){
	fac[0]=1;
	For(i,1,N) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[N]=power(fac[N],mod-2);
	Dow(i,N-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
inline int C(int n,int m){
	if (n<m||m<0) return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int n,m,l,r;
inline int calc2(int s,int lim){
	if (s<0) return 0;
	int ret=0;
	For(i,0,n-m){
		if (C(s-(lim+1)*i+n,n)==0) break;
		int tmp=1ll*C(n-m,i)*C(s-(lim+1)*i+n,n)%mod;
		if (i&1) ret=Mod(ret+mod-tmp);
			else ret=Mod(ret+tmp);
	}
	return ret;
}
inline int calc(int n,int m,int s){
	int ret=0;
	for (int i=0;(i+1)*m<=s;i++) ret=Mod(ret+Mod(calc2(s-(i+1)*m,i)+mod-calc2(s-(i+2)*m,i)));
	return Mod(C(n+s,n)+mod-1ll*ret*C(n,m)%mod);
}

int main(){
	n=read(),m=read(),l=read(),r=read(),init();
	printf("%d\n",Mod(calc(n,m,r)+mod-calc(n,m,l-1)));
}