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>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

vector<ll> fact, inv;

ll modInv(ll a, ll b = MOD-2) {
	if (b & 1) return a * modInv(a, b^1) % MOD;
	else if (b == 0) return 1;
	else return modInv(a*a % MOD, b / 2);
}
ll choose(int a, int b) {
	if (a < b) return 0;
	ll dv = inv[a-b] * inv[b] % MOD;
	return fact[a] * dv % MOD;
}

//   \sum_{v = 0}^{t} \sum_{s = 0}^{v} \sum_{c = k}^{n} -1^{c-k} (n choose k) (n-k choose c-k) ((n-1 + v-sc choose n-1) - (n-1 + v-k-sc choose n-1))
// = \sum_{c = k}^{n} -1^{c-k} (n choose k) (n-k choose c-k) \sum_{v = 0}^{t} \sum_{s = 0}^{v/c} ((n-1 + v-sc choose n-1) - (n-1 + v-k-sc choose n-1))
// = \sum_{c = k}^{n} -1^{c-k} (n choose k) (n-k choose c-k) \sum_{s = 0}^{t/c} \sum_{x = t-k-sc}^{t-sc} (n-1 + x choose n-1)
ll solve(int n, int k, int t) {
	ll res = choose(n+t, n);
	for (int c = k; c <= n; ++c) {
		ll v1 = ((c-k) % 2 ? -1 : 1) * choose(n, k) * choose(n-k, c-k) % MOD;
		ll v2 = 0;
		for (int s = 0; s*c <= t; ++s) v2 += choose(n + t - s*c, n);
		for (int s = 0; s*c <= t-k; ++s) v2 -= choose(n + t-k - s*c, n);
		res = (res - v1 * (v2 % MOD)) % MOD;
	}
	return res + MOD*(res < 0);
}

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

	int n, m, v0, v1;
	cin >> n >> m >> v0 >> v1;

	fact.resize(n + v1 + 1, 1);
	inv.resize(n + v1 + 1, 1);
	for (int i = 1; i <= n + v1; ++i) {
		fact[i] = (fact[i-1] * i) % MOD;
		inv[i] = modInv(fact[i]);
	}

	ll res = solve(n, m, v1) - solve(n, m, v0-1);
	cout << res + MOD*(res < 0) << '\n';
}