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>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cerr << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const ll MOD = TEN(9) + 7;
const int MX = TEN(6);

ll inv[MX], fact[MX], ifact[MX];

void init() {
    inv[1] = 1;
    for (int i = 2; i < MX; ++i) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    }
    fact[0] = ifact[0] = 1;
    for (int i = 1; i < MX; ++i) {
        fact[i] = fact[i-1] * i % MOD;
        ifact[i] = ifact[i-1] * inv[i] % MOD;
    }
}

ll comb(int n, int r) {
    if (n < 0 || r < 0 || r > n) return 0;
    return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}

ll solve_sub(int N, int M, int S, int r, int l) {
	ll v = 0;
	for (int i = 0; i <= N - M; ++i) {
		ll rem = S - (ll)r * M - (ll)(l + 1) * i;
		if (rem < 0) break;
		ll t = comb(rem + N, N);
		if (i % 2 == 1) {
			t *= -1;
		}

		t = t * comb(N - M, i) % MOD;
		if (t < 0) t += MOD;
		v = (v + t) % MOD;
	}
	v = v * comb(N, M) % MOD;
	return v;
}

ll solve(int N, int M, int S) {
	ll all = comb(S + N, N);
	ll ng = 0;

	for (int x = 1; (ll)x * M <= S; ++x) { //minimum of bigger part
		ll a = solve_sub(N, M, S, x, x-1) - solve_sub(N, M, S, x+1, x-1);
		ng = (ng + a) % MOD;
		if (ng < 0) ng += MOD;
	}

	return (all - ng + MOD) % MOD;
}

int main() {
	int N, M, L, R;
	cin >> N >> M >> L >> R;

	init();

	ll ans = (solve(N, M, R) - solve(N, M, L-1) + MOD) % MOD;
	cout << ans << endl;
	return 0;
}