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<iomanip>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
#include<memory>
using namespace std;
using ll=long long;

const ll MOD=1e9+7;

const int SIZE=1e6;

ll powm(ll x,ll k){
    ll res=1;
    while(k){
        if(k&1) res=res*x%MOD;
        k>>=1;
        x=x*x%MOD;
    }
    return res;
}
ll inv(ll x){
    return powm(x,MOD-2);
}
ll fact[SIZE];
ll invFact[SIZE];
void init(){
    fact[0]=1;
    for(int i=1;i<SIZE;i++){
        fact[i]=fact[i-1]*i%MOD;
    }
    invFact[SIZE-1]=inv(fact[SIZE-1]);
    for(int i=SIZE-2;i>=0;i--){
        invFact[i]=invFact[i+1]*(i+1)%MOD;
    }
}

ll comb(int n,int k){
    return fact[n]*invFact[k]%MOD*invFact[n-k]%MOD;
}
int main(){
    init();
    int n,m,l,r;
    cin>>n>>m>>l>>r;

    vector<ll> A(r+1);
    for(int i=0;i<=n-m;i++){
        for(int v=0;;v++){
            ll x=ll(v+1)*i+(v+1)*m;
            if(x>r) break;
            ll sig=(i%2==0 ? 1 : -1);
            A[x]+=sig*comb(n-m,i);
            A[x]%=MOD;
        }
    }
    for(int i=0;i<=n-m;i++){
        for(int v=0;;v++){
            ll x=ll(v)*i+(v+1)*m;
            if(x>r) break;
            ll sig=(i%2==0 ? 1 : -1);
            A[x]-=sig*comb(n-m,i);
            A[x]%=MOD;
        }
    }

    vector<ll> B(r+1);
    for(int i=0;i<=r;i++){
        B[i]=comb(n,m)*comb(i+n,n)%MOD;
    }
    
    ll res=0;
    for(int i=0 ;i<=r;i++){
        res+=A[i]*B[r-i]%MOD;
        res%=MOD;
    }
    for(int i=0;i<=l-1;i++){
        res-=A[i]*B[l-1-i]%MOD;
        res%=MOD;
    }
    ll sum=comb(r+n,n)-(l ? comb(l-1+n,n) : 0LL);
    res=sum-res;

    cout<<(res%MOD+MOD)%MOD<<endl;

    
    
    return 0;
}