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;
namespace mine
{
    #define double long double
    typedef long long ll;
    #define pr pair<int,int>
    #define FR first
    #define SE second
    #define MP make_pair
    #define PB push_back
    #define vc vector
    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num)
    {
        if(num<0) putchar('-'),num=-num;
        if(num>=10) write(num/10);
        putchar('0'+num%10);
    }
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    void chmax(int &x,const ll y) {x=(x>y?x:y);}
    void chmin(int &x,const ll y) {x=(x<y?x:y);}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):0;}
    const int INF=0x3f3f3f3f;
    const int MOD=1e9+7;
    inline int mm(const int x){return x>=MOD?x-MOD:x;}
    inline ll qpower(ll x,ll e)
    {
        ll ans=1;
        while(e)
        {
            if(e&1) ans=ans*x%MOD;
            x=x*x%MOD;e>>=1;
        }
        return ans;
    }
    inline int invm(int x){return qpower(x,MOD-2);}
    const int N=1e6+10;

    ll fac[N],facinv[N];
    int C(int n,int m){if(n<m)puts("pp");return fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;}
    int g(int n,int m){return C(n+m-1,m-1);}

    int n,m;
    int f(int R,int a,int b)
    {
        ll ans=0;
        for(int i=0;i<=m;i++)
        {
            ll tmp=R-i*ll(a+1)-ll(n-m)*b;if(tmp<0) break;
            ans=(ans+ll(i&1?MOD-1:1)*C(m,i)%MOD*g(tmp,n+1))%MOD;
        }
        return ans;
    }
    int solve(int R)
    {
        ll ans=0;
        for(int t=1;t<=R;t++) ans=mm(ans+mm( f(R,t-1,t)+MOD-f(R,t-1,t+1) ));
        return mm(g(R,n+1)+MOD-ans*C(n,m)%MOD);
    }
    void main()
    {
        fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%MOD;
        facinv[N-1]=invm(fac[N-1]);for(int i=N-2;i>=0;i--) facinv[i]=facinv[i+1]*(i+1)%MOD;

        int l,r;scanf("%d%d%d%d",&n,&m,&l,&r);
        m=n-m;//debug……
        write((solve(r)+MOD-solve(l-1))%MOD);
    }
};
int main()
{
    srand(time(0));
    mine::main();
}