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:
// https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_f
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }

const LL P = 1000000007;
const int maxN = 2 * 300000 + 5;
LL qpow(LL a, LL b) {
	LL r = 1;
	while(b) {
		if(b & 1) (r *= a) %= P;
		(a *= a) %= P; b >>= 1;
	}
	return r;
}
int m, n;
LL fac[maxN], ifac[maxN];

LL C(int n, int k) {
	if(k < 0 || k > n) return 0;
	return fac[n] * ifac[k] % P * ifac[n - k] % P;
}
LL D(int n, int k) {
	return C(n + k, k);
}

LL cnt(LL A, int n, int m, LL x) { // sum ai <= A, m of them <= x
	if(A < 0) return 0;
	LL ans = 0;
	for(int i = 0; i <= m; ++i) if(A - (x + 1) * i >= 0) {
		LL dans = D(A - (x + 1) * i, n) * C(m, i) % P;
		if(i & 1) ans -= dans; else ans += dans;
	} else {
		break;
	}
//	eprintf("cnt(%lld, %d, %d, %lld) = %lld\n", A, n, m, x, (ans % P + P) % P);
	return (ans % P + P) % P;
}

LL solve(LL A) {
	LL ans = 0;
	for(int x = 0; x <= A; ++x) if((LL)(n - m) * (x + 1) <= A) {
		ans += cnt(A - (LL)(x + 1) * (n - m), n, m, x);
		ans -= cnt(A - (LL)(x + 2) * (n - m), n, m, x);
	}
	return (ans % P + P) % P * C(n, m) % P;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	fac[0] = 1;
	for(int i = 1; i < maxN; ++i) fac[i] = fac[i - 1] * i % P;
	ifac[maxN - 1] = qpow(fac[maxN - 1], P - 2);
	for(int i = maxN - 2; i >= 0; --i) ifac[i] = ifac[i + 1] * (i + 1) % P;
	int L, R;
	cin >> n >> m >> L >> R;
	m = n - m;
	display(D(R, n) - D(L - 1, n));
	display(solve(R) - solve(L - 1));
	cout << ((D(R, n) - D(L - 1, n) - solve(R) + solve(L - 1) + P * 2) % P) << endl;
	return 0;
}