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>
#define PII pair<int, int>
#define LL long long
using namespace std;
const LL MOD = (LL) 1e9 + 7;
const int MAXN = 600005;

LL fac[MAXN], inv[MAXN];

LL qpow(LL a, LL pw) {
	LL res = 1;
	while (pw) {
		if (pw & 1) res = res * a % MOD;
		a = a * a % MOD;
		pw >>= 1;
	}
	return res;
}

LL C(int n, int k) {
	return fac[n] * inv[k] % MOD * inv[n - k] % MOD;
}

LL H(int n, int k) {
	return fac[n + k - 1] * inv[k - 1] % MOD * inv[n] % MOD;
}

LL N, M, L, R;

LL solve(LL S) {
	LL n1 = M, n2 = N - M, all = H(S, N + 1), sub = 0;
	for (int i = 1; i * n2 <= S; i++) {
		LL dist = S - i * n2, res1 = 0, res2 = 0;
		for (int j = 0; j <= n1 && j * i <= dist; j++) {
			LL to_add = C(n1, j) * H(dist - j * i, N + 1) % MOD * (j % 2 == 1 ? -1 : 1) % MOD;
			res1 = (res1 + to_add + MOD) % MOD;
		}
		
		if (dist >= n2) {
			dist -= n2;
			for (int j = 0; j <= n1 && j * i <= dist; j++) {
				LL to_add = C(n1, j) * H(dist - j * i, N + 1) % MOD * (j % 2 == 1 ? -1 : 1) % MOD;
				res2 = (res2 + to_add + MOD) % MOD;
			}
		}
		
		LL final = (res1 - res2 + MOD) % MOD * C(N, n1) % MOD;
		sub = (sub + final) % MOD;
	}
	
	return (all - sub + MOD) % MOD;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	fac[0] = inv[0] = 1;
	for (LL i = 1; i < MAXN; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = qpow(fac[i], MOD - 2);
	}

	cin >> N >> M >> L >> R;
	M = N - M;
	cout << (solve(R) - solve(L - 1) % MOD + MOD) % MOD << '\n';

	return 0;
}