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>
using namespace std;
const int N = 600005;
const int mod = 1000000007;
int n, m, l, r;
int fact[N], ifact[N], inv[N];
inline void init_fact(int n = 600000) {
	inv[1] = 1;
	for (int i = 2; i <= n; i++)
		inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
	fact[0] = ifact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = 1ll * fact[i - 1] * i % mod;
		ifact[i] = 1ll * ifact[i - 1] * inv[i] % mod;
	}
}
inline int C(int x, int y) {
	if (x < 0 || y < 0 || x < y) return 0;
	return 1ll * fact[x] * ifact[y] % mod * ifact[x - y] % mod;
}
inline int cc(int a, int b, int s) {
	if (s < 0) return 0;
	int res = 0;
	for (int i = 0, i_end = min(s / (b + 1), n - m); i <= i_end; i++) {
		int cur = 1ll * C(n - m, i) * C(n + s - i * (b + 1), n) % mod;
		if (i & 1) cur = mod - cur;
		res = (res + cur) % mod;
	}
	return res;
}
inline int calc(int k) {
	int res = 0;
	for (int x = 1, x_end = k / m; x <= x_end; x++) {
		res = (res + (cc(x, x - 1, k - x * m) - cc(x + 1, x - 1, k - (x + 1) * m) + mod) % mod) % mod;
	}
	res = 1ll * res * C(n, m) % mod;
	return (C(n + k, n) - res + mod) % mod;
}
int main() {
	init_fact();
	scanf("%d%d%d%d", &n, &m, &l, &r);
	printf("%d\n", (calc(r) - calc(l - 1) + mod) % mod);
	return 0;
}