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>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 7e5 + 66;
ll n, m, l, r;
ll fac[N], inv[N];
const ll mo = 1e9 + 7;
ll ksm(ll x, ll y) {
	ll res = 1;
	for(; y; y >>= 1, x=x * x % mo)
		if(y & 1) res = res * x % mo;
	return res;
}
void init(int tot) {
	fac[0] = inv[0] = 1;
	for(int i = 1; i <= tot; ++i) {
		fac[i] = fac[i - 1] * i % mo;
		inv[i] = ksm(fac[i], mo - 2);
	}
}
ll C(int n, int m) {
	if(n < m) return 0;
	return fac[n] * inv[m] % mo * inv[n - m] % mo;
}
inline ll bs(ll x) {
	x %= mo;
	if(x < 0) x += mo;
	return x;
}
inline ll add(ll &x, ll v) {
	x += v;
	if(x >= mo) x %= mo;
}
inline ll dec(ll &x, ll v) {
	x -= v;
	if(x < 0) x += mo;
}
ll cal(ll s, ll b) {
	if(s < 0) return 0;
	ll res = 0, t = 0;
	for(int i = 0; i <= n - m && t <= s; t += b,++i) {
		ll v = C(n - m, i) * C(s - t + n, n) % mo;
		if(i & 1) dec(res, v);
		else add(res, v);
	}
	return res * C(n, m) % mo;
}
ll solve(ll s) {
	ll res = C(s + n, n);
	for(int i = 0; i * m <= s; ++i)
		dec(res, bs(cal(s - i * m, i) - cal(s - (i + 1) * m, i)));
	return res;
}
int main() {
	n = read(), m = read(), l = read(), r = read();
	init(n + r);
	writeln(bs(solve(r) - solve(l - 1)));
	return 0;
}