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 F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 600000 + 10;
const int MOD = 1000000007;
const int LOG = 20;
const int INF = 1000000010;
const int delta = 11353;

int n, m, l, r, fac[N], inv[N];

int POW(int a, int b){
	 int res = 1;
	 while (b){
		if (b & 1) res = res * 1ll * a % MOD;
		b >>= 1;
		a = a * 1ll * a % MOD;
	 }
	 return res;
}

int nCr(int a, int b){
	if (a < 0 || b < 0 || a < b) return 0;
	int res = fac[a] * 1ll * inv[b] % MOD;
	res = res * 1ll * inv[a - b] % MOD;
	return res;
}

int minu(int a, int b){
	a -= b;
	if (a < 0) a += MOD;
	return a;
}

int Done(int y, int x, int RR){
	int Big = m;
	int Small = n - m;
	int R = RR - x * Big;
	if (R < 0) return 0;
	int res = 0;
	for (int j = 0; j <= Small; j++){
		if (j * y > R) break;
		int RRR = R - j * y;
		int del = nCr(RRR + n, n) * nCr(n - m, j) % MOD;
		if (j % 2 == 0) res = (res + del) % MOD;
		else res = minu(res, del);
	}
	return res;
}

int Solve(int R){
	int res = nCr(R + n, n);
	for (int i = 1; i <= R; i++){
		int Now = minu(Done(i, i, R), Done(i, i + 1, R)) * nCr(n, m) % MOD;
		res = minu(res, Now);
		//cout << i << ' ' << Now << '\n';
	}
	return res;
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> l >> r;
	fac[0] = 1;
	for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * 1ll * i % MOD;
	inv[N - 1] = POW(fac[N - 1], MOD - 2);
	//cout << nCr(6, 3) << '\n';
	for (int i = N - 2; i >= 0; i--) inv[i] = inv[i + 1] * 1ll * (i + 1) % MOD;
	//cout << nCr(6,3) << '\n';
	int ans = Solve(r) - Solve(l - 1);
	//cout << Solve(r) << ' ' << Solve(l - 1) << '\n';
	ans %= MOD;
	if (ans < 0) ans += MOD;
	cout << ans;

	return 0;
}