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;

int n, m;

const int mod = 1e9 + 7;
const int N = 6e5+100;

int fac[N] = {1, 1}, rfac[N] = {1, 1}, inv[N] = {0, 1};

int C(int n, int k) {
	return 1ll * fac[n] * rfac[k] % mod * rfac[n-k] % mod;
}

int get_2(int t, int k) {
	if (t < 0) return 0;
	int up = min(n-m, t/k);
	int res = 0;
	for (int i = 0; i <= up; i ++) {
		int c = C(n-m, i);
		if (i&1) c = mod - c;
		res = (res + 1ll * c * C(n+t-k*i, n)) % mod;
	}
	return res;
}

int get(int R) {
	int res = 0;
	int up = R / m;
	for (int k = 1; k <= up; k ++) {
		res = res + get_2(R-k*m, k) - get_2(R-k*m-m, k);
		if (res < 0) res += mod;
		if (res >= mod) res -= mod;
	}
	res = 1ll * res * C(n, m) % mod;
	res = C(n+R, R) - res;
	if (res < 0) res += mod;
	return res;
}

int main() {
	int L, R;
	for (int i = 2; i < N; i ++) {
		fac[i] = 1ll * fac[i-1] * i % mod;
		inv[i] = 1ll * (mod / i) * (mod - inv[mod%i]) % mod;
		rfac[i] = 1ll * rfac[i-1] * inv[i] % mod;
	}
	scanf("%d %d %d %d", &n, &m, &L, &R);
	int ans = get(R) - get(L-1);
	if (ans < 0) ans += mod;
	printf("%d\n", ans);
	return 0;
}