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 PYTHON3):

Solution:
MOD = 10**9+7

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

N,M,L,R = map(int,input().split())

P = [0 for i in range(R+1)]
for k in range(R+1):
  u = (R-M*(k+1))//(k+1)
  for j in range(u+1):
    P[(k+1)*j+M*(k+1)] += nCr(N-M,j)*(-1)**(j%2)
    P[(k+1)*j+M*(k+1)] %= MOD
for k in range(1,R+1):
  u = (R-M*(k+1))//k
  for j in range(u+1):
    P[k*j+M*(k+1)] -= nCr(N-M,j)*(-1)**(j%2)
    P[k*j+M*(k+1)] %= MOD

Q = [nCr(i+N,N) for i in range(R+1)]

def f(MAX):
  ans = 0
  for t in range(MAX+1):
    ans += P[t]*Q[MAX-t]
    ans %= MOD
  return ans

def F(x):
  return (Q[x]-nCr(N,M)*f(x))%MOD

print((F(R)-F(L-1))%MOD)