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 rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;

int fac[600005], ifac[600005];
int comb(int n, int m)
{
	return n < m ? 0 : 1LL * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

int n, m, l, r;
int f(int x)
{
	return (comb(r - x + n, n) - comb(l - 1 - x + n, n) + MOD) % MOD;
}

int main()
{
	fac[0] = 1;
	rep1(i, 600000) fac[i] = 1LL * fac[i - 1] * i % MOD;
	rep1(i, 600000) ifac[i] = i == 1 ? 1 : MOD - 1LL * ifac[MOD % i] * (MOD / i) % MOD;
	ifac[0] = 1;
	rep1(i, 600000) ifac[i] = 1LL * ifac[i - 1] * ifac[i] % MOD;
	
	scanf("%d%d%d%d", &n, &m, &l, &r);
	m = n - m;
  
	int ans = 0;
	rep1(x, r) for(int j = 0; j <= m && 1LL * (n - m + j) * x <= r; j ++)
	if(j & 1) ans = (ans - 1LL * comb(m, j) * comb(n, m) % MOD * f((n - m + j) * x) % MOD + MOD) % MOD; 
	else ans = (ans + 1LL * comb(m, j) * comb(n, m) % MOD * f((n - m + j) * x)) % MOD;
	
	rep1(x, r) for(int j = 0; j <= m && 1LL * (n - m) * (x + 1) + 1LL * j * x <= r; j ++)
	if(j & 1) ans = (ans + 1LL * comb(m, j) * comb(n, m) % MOD * f((n - m) * (x + 1) + j * x)) % MOD; 
	else ans = (ans - 1LL * comb(m, j) * comb(n, m) % MOD * f((n - m) * (x + 1) + j * x) % MOD + MOD) % MOD;
	
	ans = (f(0) - ans + MOD) % MOD;
	printf("%d\n", ans);
	return 0;
}