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 <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 3e6 + 10;
int N , M , L , R;
ll fac[maxn] , ifac[maxn]; //fac[i] = i! % mod , ifac[i] * fac[i] = 1 % mod
// count number of seq of A1 ... AN , Ai is non negative st
// 1. L <= A1 + A2 + ... + AN <= R
// 2. AM = AM + 1 , A1 >= A2 >= ... >= AN after sorting

ll qpow(ll a , int n){ //a ^ n % mod
  if(n <= 0)return 1ll;
  ll ret = qpow(a , n / 2);
  if(n % 2 == 1){
    return ((ret * ret) % mod) * a % mod;
  }
  return ret * ret % mod;
}

ll C(int n , int r){
  return (fac[n] * ifac[r] % mod) * ifac[n - r] % mod;
}

ll G(int N , int M , int S , int x , int y){ // A1 ... AM are at least x and AM+1 ... AN are less than y
  if(1ll * x * M > S)return 0ll;
  S -= x * M;
  ll ret = 0;
  ll sign = 1ll;
  for(int k = 0; k <= N - M && S >= 0; ++k , sign = 1ll * sign * (mod - 1) % mod , S -= y){
    ret = (ret + sign * C(S + N , N) % mod * C(N - M , k) % mod + mod) % mod;
  }
  return ret * C(N , M) % mod;
}

ll F(int N , int M , int S){
  ll ret = C(N + S , N);
  for(int x = 0; x < S; ++x){
    ll c = (G(N , M , S , x , x) - G(N , M , S , x + 1 , x) + mod) % mod;
    ret = (ret - c + mod) % mod;
  }
  return ret;
}

int main(){
  cin >> N >> M >> L >> R;
  fac[0] = 1ll;
  for(int i = 1; i < maxn; ++i){
    fac[i] = fac[i - 1] * i % mod;
  }
  ifac[maxn - 1] = qpow(fac[maxn - 1] , mod - 2);
  for(int i = maxn - 2; i >= 0; --i){
    ifac[i] = ifac[i + 1] * (i + 1) % mod;
  }
  cout << (F(N , M , R) - F(N , M , L - 1) + mod) % mod << endl;
  return 0;
}