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;
const int BASE = 1e9 + 7;

long long fact[600600], invFact[600600];

long long power(long long x, long long y)
{
  if (!y)
    return 1;
  long long res = power(x, y >> 1);
  res = res * res % BASE;
  if (y & 1)
    res = res * x % BASE;
  return res;
}

long long c(int n, int k)
{
  return n < k ? 0 : fact[n] * invFact[k] % BASE * invFact[n - k] % BASE;
}

// m numbers >= x, rest <= y
long long calc(int n, int m, int r, int x, int y)
{
  long long res = 0;
  // i of n - m > y
  for (int i = 0; i <= n - m; i++)
  {
    int rem = r - x * m - i * (y + 1);
    if (rem < 0)
      break;
    long long ways = c(n + rem, n) * c(n - m, i) % BASE;
    if (i % 2) res = (res - ways + BASE) % BASE;
    else res = (res + ways) % BASE;
  }
  return res;
}

long long solve(int n, int m, int r)
{
  long long res = c(n + r, n), bad = 0;
  for (int x = 1; x * m <= r; x++)
    bad = (bad + calc(n, m, r, x, x - 1) - calc(n, m, r, x + 1, x - 1) + BASE) % BASE;
  bad = bad * c(n, m) % BASE;
  return (res - bad + BASE) % BASE;
}

int main()
{
  for (int i = 0; i <= 600000; i++)
  {
    fact[i] = i ? fact[i - 1] * i % BASE : 1;
    invFact[i] = power(fact[i], BASE - 2);
  }

  int m, n, l, r;
  cin >> n >> m >> l >> r;
  cout << (solve(n, m, r) - solve(n, m, l - 1) + BASE) % BASE << endl;
}