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>

typedef long long ll;
const int maxn = 2e6 + 3;
const ll mo = 1e9 + 7;

ll mpow(ll a, ll k) {
	ll ans = 1;
	while(k > 0) {
		if(k & 1)
			ans = ans * a % mo;
		a = a * a % mo;
		k >>= 1;
	}
	return ans;
}

ll frac[maxn], rfrac[maxn];

ll C(int u, int v) {
	if(v < 0 || v > u)
		return 0;
	return frac[u] * rfrac[v] % mo * rfrac[u - v] % mo;
}

inline ll unbounded(int s, int n) {
	// sum_{a_i} = s, and 0 \le a_i
	return C(s + n - 1, n - 1);
}

ll bounded(int s, int n, int u) {
	// sum_{a_i} = s for 0 \le i < n
	// and 0 \le a_i < u for 0 \le i < n
	ll ans = unbounded(s, n);
	for(int k = 1; k <= n && k * u <= s; ++k) {
		ans = (ans + ((k & 1) ? -1 : 1) * C(n, k) * unbounded(s - k * u, n)) % mo;
	}
	return ans;
}

ll boundedPrevM(int s, int n, int u, int m) {
	// sum_{a_i} = s for 0 \le i < n
	// and 0 \le a_i < u for 0 \le i < m, 0 \le a_i for m \le i
	if(s < 0 || u <= 0 || m > n)
		return 0;
	ll ans = unbounded(s, n);
	for(int k = 1; k <= m && k * u <= s; ++k) {
		ans = (ans + ((k & 1) ? -1 : 1) * C(m, k) * unbounded(s - k * u, n)) % mo;
	}
	// fprintf(stderr, "boundedPrevM: %d %d %d %d: %d\n", s, n, u, m, ans);
	return ans;
}

ll solve(int n, int m, int s) {
	ll ans = unbounded(s, n + 1);
	for(int i = 0; i <= s + 1 && i * (ll)(n - m) <= s; ++i) {
		ans = (ans - (
				boundedPrevM(s - i * (n - m), n + 1, i, m) -
				((i + 1) * (ll)(n - m) <= s ? boundedPrevM(s - (i + 1) * (n - m), n + 1, i, m) : 0)
			) * C(n, m)) % mo;
	}
	return ans;
}

int main() {
	frac[0] = 1;
	for(int i = 1; i < maxn; ++i)
		frac[i] = frac[i - 1] * (ll)i % mo;
	rfrac[maxn - 1] = mpow(frac[maxn - 1], mo - 2);
	for(int i = maxn - 2; i >= 0; --i)
		rfrac[i] = rfrac[i + 1] * (ll)(i + 1) % mo;

	int n, m, l, r;
	scanf("%d%d%d%d", &n, &m, &l, &r);
	printf("%lld\n", ((solve(n, n - m, r) - solve(n, n - m, l - 1)) % mo + mo) % mo);
	return 0;
}