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 int N=300000,mod=1000000007;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

int n,m,l,r;

void into(){
  scanf("%d%d%d%d",&n,&m,&l,&r);
}

int inv[N*2+9],fac[N*2+9],ifac[N*2+9];

void Get_inv(){
  inv[1]=1;
  fac[0]=fac[1]=1;
  ifac[0]=ifac[1]=1;
  for (int i=2;i<=n+r;++i){
	inv[i]=mul(mod-mod/i,inv[mod%i]);
	fac[i]=mul(fac[i-1],i);
	ifac[i]=mul(ifac[i-1],inv[i]);
  }
}

int Get_c(int n,int m){return n<m||m<0?0:mul(fac[n],mul(ifac[m],ifac[n-m]));}

int Get_ans(int x,int mx){
  int res=0;
  mx-=m*x;
  for (int i=0;i<=n-m&&i*x<=mx;++i){
	int t=mul(Get_c(n-m,i),Get_c(mx-i*x+n,n));
	i&1?ssub(res,t):sadd(res,t);
  }
  if (--x<=0) return mul(Get_c(n,m),res);
  for (int i=0;i<=n-m&&i*x<=mx;++i){
	int t=mul(Get_c(n-m,i),Get_c(mx-i*x+n,n));
	i&1?sadd(res,t):ssub(res,t);
  }
  return mul(Get_c(n,m),res);
}

int ans;

void Get_ans(){
  for (int i=l;i<=r;++i) sadd(ans,Get_c(i+n-1,n-1));
  for (int i=1;i<=r&&m*i<=r;++i) ssub(ans,Get_ans(i,r));
  for (int i=1;i<l&&m*i<l;++i) sadd(ans,Get_ans(i,l-1));
}

void work(){
  Get_inv();
  Get_ans();
}

void outo(){
  printf("%d\n",ans);
}

int main(){
  into();
  work();
  outo();
  return 0;
}