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>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int n, m, l, r;

Int fact[1080000];
Int revfact[1080000];
Int rev[1080000];

void init(){
    Int m = MOD;
    fact[0] = 1;
    revfact[0] = 1;
    rev[0] = 0;
    rev[1] = 1;
    for(int i = 1;i < 1080000;i++){
        fact[i] = fact[i-1] * i % m;
        if(i>1)rev[i] = MOD / i * (MOD-rev[MOD % i]) % MOD;
        revfact[i] = revfact[i-1] * rev[i] % MOD;
    }
}

Int nCk(Int n, Int k){
    if(n < k)return 0;
    return fact[n] * revfact[n-k] % MOD * revfact[k] % MOD;
}



Int solve2(Int n, Int m, Int r, Int b, Int a){
    Int res = 0;
    for(Int i = 0;i <= n-m;i++){
        Int rest = r - m * a - i * (b+1);
        if(rest < 0)break;
        Int tmp = nCk(rest + n, n) * nCk(n, m) % MOD * nCk(n-m, i) % MOD;
        if(i % 2)tmp *= -1;
        res += tmp;res %= MOD;
    }
    if(res < 0)res += MOD;

    return res;
}

Int solve(Int n, Int m, Int r){
    Int res = nCk(r + n, n);
    for(int i = 0;i <= r;i++){
        res -= (solve2(n, m, r, i, i+1) - solve2(n, m, r, i-1, i+1)) % MOD;res %= MOD;
    }
    if(res < 0)res += MOD;
    return res;
}

int main(){
    init();
    cin >> n >> m >> l >> r;
    Int res = solve(n, m, r);
    if(l)res -= solve(n, m, l-1);
    res %= MOD;
    if(res < 0)res += MOD;
    cout << res << endl;
    return 0;
}