//BOJ_2092_집합의개수

import java.io.*;

class Main {
    static int T, A, S, B;
    static int[] count;
    static int[][] dp = new int[201][4001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");

        T= Integer.parseInt(s[0]);
        A= Integer.parseInt(s[1]);
        S= Integer.parseInt(s[2]);
        B= Integer.parseInt(s[3]);

        s = br.readLine().split(" ");

        count = new int[T+1];
        for(int i=0;i<A;i++){
            count[Integer.parseInt(s[i])]++;
        }

        for(int i=1;i<=T;i++){
            for(int j=0;j<=count[i];j++){
                dp[i][j] = 1;
            }//숫자 1개로 만들 수 있는 수들 갯수(1이면 공집합, 1, 11, 111, ...) 결국 하나씩 가능

            for(int j=1;j<=A;j++){
                dp[i][j] += dp[i-1][j]; //바로 이전꺼(1개로 만들 수 있는 그 조합들) 갯수 지금꺼에 추가시킴.

                //핵심 : 새로운 조합 만들기(예를 들어, 앞에서 어떤 조합들이 만들어져있다고 가정하고, 거기에 지금 숫자를 추가해서 새로운 조합 생성)
                for(int k=1;k<=count[i];k++){
                    if(k<j){
                        dp[i][j] += dp[i-1][j-k];
                        dp[i][j]%=1000000;
                    }
                }
            }
        }

        int res = 0;
        for(int i=S;i<=B;i++){
            res += dp[T][i]%1000000;
        }
        System.out.println(res%1000000);
    }
}