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;

using ll = long long;

template<int MOD>
struct ModInt {
   using Mint = ModInt;
   int val;
   ModInt(ll __val = 0) { fix(__val % MOD + MOD); }
   Mint& fix(int __val) { val = __val; if (val >= MOD) val -= MOD; return *this; }
   explicit operator int() { return val; }
   Mint operator + (const Mint &mt) const { return Mint().fix(val + mt.val); }
   Mint operator - (const Mint &mt) const { return Mint().fix(val - mt.val + MOD); }
   Mint operator * (const Mint &mt) const { return Mint().fix(ll(val) * mt.val % MOD + MOD); }
   Mint& operator += (const Mint &mt) { return *this = *this + mt; }
   Mint& operator -= (const Mint &mt) { return *this = *this - mt; }
   Mint& operator *= (const Mint &mt) { return *this = *this * mt; }
   Mint pow(int y) const {
      Mint x = *this;
      Mint ans(1);
      for (; y > 0; y >>= 1, x *= x) {
         if (y & 1) ans *= x;
      }
      return ans;
   }
   Mint operator -() const { return Mint().fix(MOD - val); }
   Mint inv() const { return pow(MOD - 2); }
   Mint operator / (const Mint &mt) const { return *this * mt.inv(); }
   Mint& operator /= (const Mint &mt) const { return *this / mt; }
   friend ostream& operator<<(ostream& os, const Mint& mt) { return os << mt.val; }
};

using Mint = ModInt<1000000007>;

const int MAXN = 1000100;

Mint fact[MAXN], ifact[MAXN];

void precalc() {
   fact[0] = 1;
   for (int i = 1; i < MAXN; ++i) fact[i] = fact[i - 1] * i;
   ifact[MAXN - 1] = fact[MAXN - 1].inv();
   for (int i = MAXN - 1; i > 0; --i) ifact[i - 1] = ifact[i] * i;
}

Mint C(int N, int K) {
   if (K < 0 || N < K) return 0;
   return fact[N] * ifact[K] * ifact[N - K];
}

Mint ways(int N, int M, int R, int val) {
   Mint ans = 0;
   for (int z = 0; z <= M; ++z) {
      int curR = R - z * val;
      if (curR < 0) break;
      Mint cur = C(M, z) * C(N + curR, N);
      if (z & 1) ans -= cur;
      else ans += cur;
   }
   return ans;
}

Mint solve(int N, int M, int R) {
   Mint ans = C(N + R, N);
   for (int val = 1; val <= R; ++val) {
      int curR = R - M * val;
      if (curR < 0) break;
      ans -= C(N, M) * (ways(N, N - M, curR, val) - ways(N, N - M, curR - M, val));
   }
   return ans;
}

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   precalc();
   int N, M, L, R;
   cin >> N >> M >> L >> R;
   cout << solve(N, M, R) - solve(N, M, L - 1) << "\n";
}