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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
typedef long long ll;

template <typename Tp> inline void getint(Tp &num){
	register int ch, neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch & 15;
	while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
	if(neg) num = -num;
}

inline int kazu(int a, const int &b) {return (a += b) >= MOD ? a - MOD : a;}
inline int hiku(int a, const int &b) {return (a -= b) < 0 ? a + MOD : a;}

inline ll fastpow(ll bas, ll ex){
	register ll res = 1; bas %= MOD;
	for(; ex; ex >>= 1, bas = bas * bas % MOD) if(ex & 1) res = res * bas % MOD;
	return res;
}

int N, M, L, R;
ll fac[600005] = {1}, ifac[600005];

inline void initfac(const int &lim){
	for(register int i = 1; i <= lim; i++) fac[i] = fac[i - 1] * i % MOD;
	ifac[lim] = fastpow(fac[lim], MOD - 2);
	for(register int i = lim; i >= 1; i--) ifac[i - 1] = ifac[i] * i % MOD;
}

inline ll C(const int &n, const int &m) {return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;}

inline int calc2(int S, const int &l, const int &r){
	if(S < M * (ll)r) return 0; int res = 0; S -= M * r;
	for(register int i = 0, sgn = 1; i <= N - M && S >= 0; i++, sgn = sgn * (MOD - 1LL) % MOD, S -= l)
		res = kazu(res, sgn * C(S + N, N) % MOD * C(N - M, i) % MOD);
	return res * C(N, M) % MOD;
}
/*	∑A[i] + B = S, A[1 .. M] >= r, 0 <= A[M + 1 .. N] < l
==>	∑A[i] + B = S - M * r, A[1 .. M] >= 0, 0 <= A[M + 1 .. N] < l */

inline int calc(const int &S){
	int res = C(S + N, N);
	for(register int i = S; i > 0; i--) res = hiku(res, hiku(calc2(S, i, i), calc2(S, i, i + 1)));
	return res;
}
/*	∑A[i] <= S
==>	∑A[i] + B = S */

int main(){
	getint(N), getint(M), getint(L), getint(R), initfac(R + N);
	return printf("%d\n", hiku(calc(R), calc(L - 1))), 0;
}