#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <sstream>
#include <math.h> 
#include <string.h>
#include <algorithm>
#include <numeric>
#include <deque>
#include <climits>

using namespace std;

typedef long long ll;

// const double M_PI = acos(-1.0);
// const double E = 2.71828182845904523536029;

const int MAX_ANT = 10010;
ll MD = 1000000;

ll dp[MAX_ANT];

int main() {
	int t, a, s, b;
	cin >> t >> a >> s >> b;
	vector<int> ants(t + 1);
	for (int i = 0; i < a; i++) {
		int ant; cin >> ant;
		ants[ant]++;
	}

	for (int family = 1; family <= t; family++) {
		int familySize = ants[family];
		for (int set = a; set >= 1; set--) {
			ll setSize = dp[set] - dp[set - 1];
			if (familySize >= set) {
				setSize += 1;
			}

			int s = max(set - familySize - 1, 0);
			int e = set - 1;
			setSize = dp[e] - dp[s] + MD + setSize;
			
			dp[set] = setSize % MD;
		}

		for (int i = 1; i <= a; i++) {
			dp[i] = (dp[i] + dp[i - 1]) % MD;
		}
	}

	cout << (dp[b] - dp[s-1] + MD) % MD << endl;
	return 0;
}