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 <cstdio>
#define ll long long
ll n, m, l, r, c1[300001], c2[600001], c3, mod = 1000000007;
ll big(ll b, ll p){
	if (p == 1) return b;
	ll h = big(b, p / 2);
	ll res = (h * h) % mod;
	if (p % 2 == 1) res = (res * b) % mod;
	return res;
}
void init(){
	c1[0] = 1;
	for (int i = 1; i <= n - m; i++){
		c1[i] = (c1[i - 1] * (n - m - i + 1)) % mod;
		c1[i] = (c1[i] * big(i, mod - 2)) % mod;
	}
	for (int i = 0; i < n; i++) c2[i] = 0;
	c2[n] = 1;
	for (int i = n + 1; i <= n + r; i++){
		c2[i] = (c2[i - 1] * i) % mod;
		c2[i] = (c2[i] * big(i - n, mod - 2)) % mod;
	}
	c3 = 1;
	for (int i = 1; i <= m; i++){
		c3 = (c3 * (n - i + 1)) % mod;
		c3 = (c3 * big(i, mod - 2)) % mod;
	}
}
ll f(ll k){
	ll sum = 0;
	for (ll x = 1; x <= k; x++){
		for (ll i = 0; k - x * m - x * i >= 0; i++){
			if (i > n - m) break;
			ll t = k - x * m - x * i + n;
			sum += mod + ((i % 2 == 0) ? 1 : -1) * ((c1[i] * (((t - m < 0) ? 0 : c2[t - m]) - c2[t])) % mod);
			sum %= mod;
		}
	}
	sum = (sum * c3) % mod;
	return (c2[n + k] + sum) % mod;
}
int main(){
	scanf("%lld %lld %lld %lld", &n, &m, &l, &r);
	init();
	printf("%lld\n", (f(r) + mod - f(l - 1)) % mod);
}