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:
// ※※※ 解答不能 ※※※
// 以下のソースを勉強する.
// yutaka1999氏.
// https://atcoder.jp/contests/jsc2019-qual/submissions/7117252
#include <bits/stdc++.h>
using namespace std;
#define SIZE 600005
#define MOD 1000000007
using LL = long long;
using P = pair<int, int>;

LL inv[SIZE], fac[SIZE], finv[SIZE];
void make(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < SIZE; i++){
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fac[i] = fac[i - 1] * (LL)i % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

LL C(int a,int b){
    if(a < b) return 0;
    return fac[a] * (finv[b] * finv[a - b] % MOD) % MOD;
}

LL solve(int n, int m, int L){
    LL ret=C(n + L, n);
    for(int t = 0; (t + 1) * m <= L; t++){
        int zan = L - (t + 1) * m;
        int a = n - m, b = m;
        for(int k = 0; k * t <= L && k <= a; k++){
            if(zan < 0) break;
            LL vl = C(zan + n, n) * C(a, k) % MOD * C(n, a) % MOD;
            if(k % 2 == 1) ret += vl;
            else           ret += MOD - vl;
            ret %= MOD;
            zan -= t + 1;
        }
        zan = L - (t + 2) * m;
        for(int k = 0; k * t <= L && k <= a; k++){
            if(zan < 0) break;
            LL vl = C(zan + n, n) * C(a, k) % MOD * C(n, a) % MOD;
            if(k % 2 == 0) ret += vl;
            else           ret += MOD - vl;
            ret %= MOD;
            zan -= t + 1;
        }
    }
    return ret;
}
int main(){
    make();
    int n, m, l, r;
    scanf("%d %d %d %d",&n, &m, &l, &r);
    printf("%lld\n",(solve(n, m, r) - solve(n, m, l - 1) + MOD) % MOD);
    return 0;
}