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<cstdio>
const int MAXN = 1000000;
const int MOD = int(1E9) + 7;
int pow_mod(int b, int p) {
	int ret = 1;
	while( p ) {
		if( p & 1 ) ret = 1LL*ret*b%MOD;
		b = 1LL*b*b%MOD;
		p >>= 1;
	}
	return ret;
}
int fct[MAXN + 5], ifct[MAXN + 5];
void init() {
	fct[0] = 1;
	for(int i=1;i<=MAXN;i++)
		fct[i] = 1LL*fct[i-1]*i%MOD;
	ifct[MAXN] = pow_mod(fct[MAXN], MOD-2);
	for(int i=MAXN-1;i>=0;i--)
		ifct[i] = 1LL*ifct[i+1]*(i+1)%MOD;
}
int comb(int n, int m) {return 1LL*fct[n]*ifct[m]%MOD*ifct[n-m]%MOD;}
int solve2(int N, int M, int S, int l, int r) {
	int ret = 0;
	if( S - 1LL*M*r < 0 ) return ret;
	else S -= M*r;
	for(int i=0,f=1;i<=N-M&&S>=0;i++,f=1LL*f*(MOD-1)%MOD,S-=l)
		ret = (ret + 1LL*f*comb(S + N, N)%MOD*comb(N - M, i)%MOD)%MOD;
	return 1LL*ret*comb(N, M)%MOD;
}
//A1 + A2 + ... + AN + B = S, A[1...M] >= r, 0 <= A[M+1...N] < l
//A1 + A2 + ... + AN + B = S - M*r, A[1...M] >= 0, 0 <= A[M+1...N] < l
int solve(int N, int M, int S) {
	int ret = comb(S + N, N);
	for(int i=S;i>=1;i--) {
		int del = (solve2(N, M, S, i, i) + MOD - solve2(N, M, S, i, i + 1))%MOD;
		ret = (ret + MOD - del)%MOD;
	}
	return ret;
}
//A1 + A2 + ... + AN + B = S
int main() {
	init(); int N, M, L, R;
	scanf("%d%d%d%d", &N, &M, &L, &R);
	printf("%d\n", (solve(N, M, R) + MOD - solve(N, M, L - 1))%MOD);
}