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 <cstdio>

/*

[p^N] N! exp(Np) = N^N

************
*********
ooooooo
******
****
***
**

N! [q^{L...R}] \sum_{k=0}^R ([p^{M-1}] exp(p(q^{k+1} + q^{k+2} + ... + q^R)) (exp(p q^k) - 1)/p) ([p^{N-M}] exp(p (1 + q + q^2 + ... + q^{k-1})))
N! [q^{L...R}] \sum_{k=0}^R ([p^{M}] exp(pq^{k}/(1-q)) - exp(pq^{k+1}/(1-q))) ([p^{N-M}] exp(p (1-q^k) / (1-q)))
N! [q^{L...R}] \sum_{k=0}^R ((q^k/(1-q))^M - (q^{k+1}/(1-q))^M) / M! ((1-q^k) / (1-q))^{N-M} / (N-M)!
\binom{N}{M} [q^{L...R}] 1/(1-q)^N \sum_{k=0}^R (q^{kM} - q^{(k+1)M}) (1-q^k)^{N-M}
\binom{N}{M} [q^R] (1-q^{R-L+1})/(1-q) 1/(1-q)^N \sum_{k=0}^R (q^{kM} - q^{(k+1)M}) (1-q^k)^{N-M}
\binom{N}{M} [q^R] (1-q^{R-L+1}) 1/(1-q)^{N+1} \sum_{k=0}^R q^{kM)} (1- q^M) (1-q^k)^{N-M}
\binom{N}{M} [q^R] (1-q^{R-L+1}) (1-q^M)/(1-q)^{N+1} \sum_{k=0}^R q^{kM} (1-q^k)^{N-M}

N! [q^{L...R}] [p^N] exp(p (1 + q + q^2 + ... + q^R))
N! [q^{L...R}] 1/(1-q)^N / N!
[q^R] (1-q^{R-L+1})/(1-q) 1/(1-q)^N
[q^R] (1-q^{R-L+1}) 1/(1-q)^{N+1}
\binom{N+R}{R} - \binom{N+L-1}{L-1}
*/

constexpr int mod = 1000000007;
constexpr int MAX = 600000;
int fact[MAX+1];
int ifact[MAX+1];
long long int dp[MAX+1];

int pow(int x, int n){
  int r = 1;
  for(; n; n >>= 1){
    if(n&1) r = (long long) r * x % mod;
    x = (long long) x * x % mod;
  }
  return r;
}

int binom(int n, int k){
  return (long long) fact[n] * ifact[k] % mod * ifact[n-k] % mod;
}

int n, m, l, r;

int main(){
  fact[0] = 1;
  for(int i = 1; i <= MAX; i++) fact[i] = (long long) i * fact[i-1] % mod;
  ifact[MAX] = pow(fact[MAX], mod-2);
  for(int i = MAX-1; i >= 0; i--) ifact[i] = (long long) (i+1) * ifact[i+1] % mod;

  scanf("%d%d%d%d", &n, &m, &l, &r);

  for(int i = m; i <= r; i++){
    int tmp = binom(n-m, i-m);
    if((i-m)&1) tmp = mod-tmp;
    for(int j = 1; j * i <= r; j++){
      dp[j*i] += tmp;
    }
  }
  for(int i = r; i >= r-l+1; i--) dp[i] -= dp[i - (r-l+1)];
  for(int i = r; i >= m; i--) (dp[i] -= dp[i - m]) %= mod;
 
  int ans = 0;
  for(int i = 0; i <= r; i++){
    ans = (ans + (long long) dp[r - i] * binom(n+i, i)) % mod;
  }

  ans = (long long) binom(n, m) * ans % mod;
  ans = binom(n + r, r) - ans;
  if(ans < 0) ans += mod;
  ans = ans - binom(n + l - 1, l - 1);
  if(ans < 0) ans += mod;
  if(ans < 0) ans += mod;
  printf("%d\n", ans);

  return 0;
}