#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

//#include<bits/stdc++.h>

using namespace std;

int T, A, S, B;

const int maxt = 1e3+, maxa = 1e5+, mod = 1e6;

int f[][maxa];

int c[maxt];

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    scanf("%d%d%d%d",&T,&A,&S,&B);

    for(int i = A; i--;){

        int x; scanf("%d",&x);

        c[x]++;

    }

    f[][] = f[][] = ; //不选方案数为1

    for(int i = ; i <= T; i++){

        int a = i&, b = a^;

        for(int j = ; j <= B; j++){

            if(j-c[i]>){

                f[a][j] = ( f[a][j-] + f[b][j] - f[b][j--c[i]] ) % mod;

            }else {

                f[a][j] = ( f[a][j-] + f[b][j] ) % mod;

            }

        }

    }

    int sum = , *F = f[T&];

    for(int i = S; i <= B; i++){

        sum = (sum + F[i]) % mod;

    }

    printf("%d\n",sum<?sum+mod:sum);

    return ;

}