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<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}
namespace IO{
    char nc(){ static char bf[100000],*p1=bf,*p2=bf; return p1==p2&&(p2=(p1=bf)+ fread(bf,1,100000,stdin),p1==p2)?EOF:*p1++; }
    int rd(){ int res=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))res=res*10+c-'0',c=getchar(); return res; }
}/*}}}*/
/******************heading******************/
#define int lld
const int N=2*3e5+50,P=1e9+7;

int n,m,l,r;
int fac[N],fnv[N];

int pw(int a,int m,int p){
    int res=1;
    while(m)m&1?res=res*a%p:0,a=a*a%p,m>>=1;
    return res;
}
int binom(int n,int m){
    if(n<m)return 0;
    return fac[n]*fnv[m]%P*fnv[n-m]%P;
}
void init(int k){
    fac[0]=1;
    FOR(i,1,k)fac[i]=fac[i-1]*i%P;
    fnv[k]=pw(fac[k],P-2,P);
    ROF(i,k,1)fnv[i-1]=fnv[i]*i%P;
}
int calc2(int x){
    //printf("  calc2(%lld)\n",x);
    return binom(n+x,x);
}
int calc2(int a,int b,int s){
    //printf("  calc2(n=%lld,a=%lld,b=%lld,s=%lld)\n",n,a,b,s);
    //至多和为s,m个数大于等于a，n-m个数小于等于b的方案数
    if(s<m*a)return 0;
    int lim=min((s-m*a)/(b+1),n-m);
    int res=0;
    FOR(i,0,lim){//枚举n-m个数中有i个大于b
        int t=calc2(s-m*a-i*(b+1))%P*binom(n-m,i)%P;
        //printf("  i=%lld,t=%lld\n",i,t);
        res+=(1-2*(i&1))*t;
        res%=P;
    }
    res=res*binom(n,m)%P;
    //printf("  res=%lld\n",res);
    return res;
}
int calc(int a,int b,int s){
    //printf("\033[32mcalc(a=%lld,b=%lld,s=%lld)\033[0m\n",a,b,s);
    //至多和为s,第m为a，n-m个数小于等于b的方案数
    int res=calc2(a,b,s)-calc2(a+1,b,s);
    res=(res%P+P)%P;
    //printf("\033[32mres=%lld\033[0m\n",res);
    return res;
}
int calc(int s){
    //printf("calc(n=%lld,m=%lld,s=%lld)\n",n,m,s);
    int tot=binom(n+s,s);
    //printf("tot=%lld\n",tot);
    FOR(i,1,s)tot-=calc(i,i-1,s),tot%=P;
    tot+=P,tot%=P;
    return tot;
}
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&l,&r);
    init(n+r);
    printf("%lld",((calc(r)-calc(l-1))%P+P)%P);
    return 0;
}