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 <iostream>
using namespace std;

long long mod = 1000000007;
long long fact[1 << 20], inv[1 << 20];

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 33; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long Div(long long a, long long b, long long m) {
	return (a * modpow(b, m - 2, m)) % m;
}

void init() {
	fact[0] = 1;
	for (int i = 1; i <= 600000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
	for (int i = 0; i <= 600000; i++) inv[i] = Div(1, fact[i], mod);
}

long long ncr(long long n, long long r) {
	if (r < 0 || n < r) return 0;
	return (fact[n] * inv[r] % mod) * inv[n - r] % mod;
}

long long N, M, L, R;

long long solve(long long border) {
	long long V1 = ncr(N, M);
	long long V2 = 0;
	for (int i = 0; i <= N - M; i++) {
		long long cl = L - (M + i) * border + (N - 1), el = L - (M + i) * border + (N - M - 1);
		long long cr = R - (M + i) * border + (N - 1), er = R - (M + i) * border + (N - M - 1);
		if (cr < 0) break;
		if (i % 2 == 0) {
			V2 += ncr(N - M, i) * (ncr(cr + 1, N) - ncr(er + 1, N)); V2 = (V2 + mod * mod) % mod;
			V2 -= ncr(N - M, i) * (ncr(cl + 0, N) - ncr(el + 0, N)); V2 = (V2 + mod * mod) % mod;
		}
		if (i % 2 == 1) {
			V2 -= ncr(N - M, i) * (ncr(cr + 1, N) - ncr(er + 1, N)); V2 = (V2 + mod * mod) % mod;
			V2 += ncr(N - M, i) * (ncr(cl + 0, N) - ncr(el + 0, N)); V2 = (V2 + mod * mod) % mod;
		}
	}
	return V1 * V2 % mod;
}

int main() {
	cin >> N >> M >> L >> R;
	init();

	long long Answer = 0;
	for (int i = 1; i <= R; i++) {
		Answer += solve(i);
		Answer %= mod;
	}

	long long Answer2 = (ncr(R + N, N) - ncr(L + N - 1, N) + mod) % mod;
	cout << (Answer2 - Answer + mod) % mod << endl;
	return 0;
}