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 LL long long
#define pii pair<int,int>
using namespace std;
const int inf = 2147483647;
const int mod = 1e9 + 7;
const int N = 600001;

int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}
void put(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

int n, m, jc[N], inv[N];

int add(int x, int y) {x += y; return x >= mod ? x - mod : x;}
int dec(int x, int y) {x -= y; return x < 0 ? x + mod : x;}
int C(int n, int m) {return (LL)jc[n] * inv[m] % mod * inv[n - m] % mod;}
int pow_mod(int a, int k) {int ans = 1; for(; k; k >>= 1, a = (LL)a * a % mod) if(k & 1) ans = (LL)ans * a % mod; return ans;}

int gt(LL S, int rr) {
	if(S < 0) return 0;
	int ans = 0;
	for(int i = 0, t = 0; i <= S && t <= n - m; i += rr, t++) {
		if(t & 1) ans = dec(ans, (LL)C(n - m, t) * C(n + S - i, n) % mod);
		else ans = add(ans, (LL)C(n - m, t) * C(n + S - i, n) % mod);
	} return (LL)ans * C(n, m) % mod;
}

int solve(int n, int S) {
	int ans = C(n + S, n);
	for(int i = 1; i <= S; i++) ans = dec(ans, dec(gt(S - (LL)m * i, i), gt(S - (LL)m * (i + 1), i)));
	return ans;
}

int main() {
	n = read(), m = read(); int l = read(), r = read();
	jc[0] = 1; for(int i = 1; i <= n + r; i++) jc[i] = (LL)jc[i - 1] * i % mod;
	inv[n + r] = pow_mod(jc[n + r], mod - 2); for(int i = n + r; i >= 1; i--) inv[i - 1] = (LL)inv[i] * i % mod;
	put(dec(solve(n, r), solve(n, l - 1)));
	return 0;
}