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;
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 6000000 + 10;
int inv[N],fac[N];
int n,m,l,r;
LL C(int x,int y){
    return 1LL*fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
LL F(int n,int S){
    ++ n;
    return C(S+n-1,n-1);
}
LL solve(int S,int x,int a,int y,int b) {
    // printf("solve S=%d, x=%d, a=%d, y=%d, b=%d\n", S,x,a,y,b);
    LL ans = 0;
    // x<=a, y>=b
    for(int i=0;i<=x;i++){
        // i >= a+1, y >= b
        LL rem = S - 1LL*(a+1)*i - 1LL*y*b;
        if(rem < 0) {
            // printf("! ans=%lld\n",ans);
            return ans * C(x+y,x) % MOD;
        }
        ans += (i%2?-1:1) * C(x,i) % MOD * F(x+y, rem);
        //printf("i=%d, ans=%lld\n", i,ans);
        ans = (ans % MOD + MOD) % MOD;
    }
   // printf("ans=%lld\n", ans);
    return ans * C(x+y,x) % MOD;
}
LL cac(int S) {
    // a1+a2+...+an <= S
    // m >= x 且下界可以取到 
    // n-m <= x-1
    LL ans=0;
    for(int x=1;x<=S;x++){
        ans=(ans-solve(S,n-m,x-1,m,x+1)+solve(S,n-m,x-1,m,x)+MOD)%MOD;
        // printf("ans = %lld\n", ans);
    }
    // printf("S = %d, ans = %lld\n", S, ans);
    return (ans%MOD+MOD)%MOD;
}
int main() {
    inv[1]=1;
    for(int i=2;i<N;i++){
        inv[i]=(MOD-(MOD/i))*inv[MOD%i]%MOD;
    }
    inv[0]=1;fac[0]=1;
    for(int i=1;i<N;i++){
        inv[i]=1LL*inv[i-1]*inv[i]%MOD;
        fac[i]=1LL*fac[i-1]*i%MOD;
    }
    scanf("%d%d%d%d",&n,&m,&l,&r);
    //return !printf("# %lld\n", cac(r));
    LL res=(cac(r)-cac(l-1)+MOD)%MOD;
    LL tot=(F(n,r)-F(n,l-1)+MOD)%MOD;
    // printf("%lld %lld\n", res, tot);
    res=(tot-res+MOD)%MOD;
    cout<<res<<endl;
}