10 2 5
1 1 1 2 2 2 2 2 2 2
 10 2 5
1 1 1 1 1 1 2 2 2 2
 3 3 2
1 3 1
 8 8 7
7 2 8 6 8 5 3 8
 7 7 5
2 6 3 6 3 5 1
 5 5 1
5 2 5 1 2
 6 6 6
5 6 5 3 4 2
 5 5 2
2 3 2 2 4
 3 3 3
1 1 1
 111 78 54
24 13 49 22 52 38 38 63 21 10 9 56 60 47 11 78 23 52 55 12 72 33 17 14 33 59 21 32 20 73 1 60 27 64 23 74 36 49 69 14 29 37 19 61 52 33 26 27 10 11 34 25 62 47 36 12 63 45 31 71 78 1 6 26 36 65 56 46 19 28 77 64 56 8 77 38 3 33 63 77 40 7 22 13 60 14 57 43 51 10 30 21 7 67 32 11 12 9 72 24 27 67 25 63 6 67 69 37 26 19 26
 10 2 5
1 1 1 1 1 1 1 1 1 2
 6 6 1
4 5 6 3 5 3
 10 2 5
1 1 1 1 2 2 2 2 2 2
 8 8 3
8 8 2 7 8 2 3 5
 7 7 4
4 6 6 7 2 5 3
 10 2 5
2 2 2 2 2 2 2 2 2 2
 111 67 97
32 67 4 15 17 17 23 6 39 54 19 62 28 59 63 36 44 40 28 67 28 3 55 19 11 26 3 38 22 26 62 54 61 15 22 4 47 53 27 36 31 5 16 59 51 62 51 46 7 55 26 66 50 51 32 17 54 14 18 14 40 30 24 2 61 16 16 27 55 58 35 7 26 3 26 4 13 59 14 32 56 54 5 46 39 30 45 24 37 12 67 38 45 32 41 21 46 26 41 29 15 28 65 5 19 53 13 31 58 18 57
 6 6 2
4 4 2 4 2 3
 10 2 5
1 1 1 1 1 2 2 2 2 2
 10 2 5
1 1 1 1 1 1 1 1 2 2
 6 6 4
5 2 4 3 1 5
 10 2 5
1 1 2 2 2 2 2 2 2 2
 1 1 1
1
 8 8 5
7 5 6 8 2 8 3 4
 10 2 5
1 1 1 1 1 1 1 2 2 2
 111 101 52
54 69 33 81 8 90 48 21 96 35 44 75 68 34 101 82 93 94 86 76 33 91 5 70 22 84 70 71 62 81 50 83 51 43 95 46 19 53 101 34 51 40 6 17 69 60 73 89 65 75 59 68 62 49 89 23 63 83 86 68 62 39 1 18 3 75 44 57 9 24 67 81 83 45 93 66 79 71 43 49 17 2 33 38 98 71 71 21 56 16 31 2 75 61 64 38 69 80 81 12 68 95 26 9 69 82 41 35 75 7 71
 3 3 3
3 3 1
 4 4 2
2 4 4 3
 10 2 5
1 2 2 2 2 2 2 2 2 2
 4 4 4
4 4 4 4
 3 3 2
1 2 3
 2 1 2
1 1
 5 5 3
3 4 1 5 5
 7 7 1
2 6 5 6 2 3 3
 111 9 57
9 9 2 6 8 6 5 8 9 7 3 9 1 2 6 6 5 3 1 1 6 1 8 4 3 9 8 6 8 1 9 8 5 8 6 9 4 5 7 3 1 6 4 3 2 5 7 3 1 7 9 1 7 1 3 5 9 5 6 2 2 7 9 7 1 5 5 5 5 2 6 5 7 3 8 9 7 3 6 5 1 9 2 9 9 8 8 7 9 1 6 2 4 5 7 4 8 9 9 2 7 7 6 9 8 2 1 3 3 1 5
 4 4 1
2 4 1 4
 2 1 1
1 1
 111 16 58
15 6 4 7 7 10 16 2 3 1 4 8 10 1 2 11 6 6 14 16 6 16 1 2 13 2 7 13 1 4 1 4 12 2 4 11 15 12 9 13 10 4 11 7 5 3 12 11 11 3 16 15 9 6 15 11 4 14 8 15 16 3 9 10 9 1 8 4 14 7 13 5 1 8 5 11 8 14 1 8 15 2 5 2 4 5 9 2 10 11 11 5 7 11 11 14 5 16 14 2 4 11 12 10 7 14 2 5 3 2 1
 2 2 2
1 1

4
 5
 2
 6
 12
 3
 1
 4
 1
 648
 2
 4
 5
 19
 25
 1
 214
 5
 6
 3
 11
 3
 1
 41
 4
 881
 1
 4
 2
 1
 3
 1
 7
 4
 446
 3
 1
 552
 1

import java.io.*;
import java.util.*;

public class F3
{
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok;
    Complex[] aux1, aux2;
    double[] sin, cos;

    public void go() throws IOException
    {
        sin = new double[100];
        cos = new double[100];
        for (int i = 0; i < 100; i++) {
            sin[i] = Math.sin(Math.PI * 2 / (1 << i));
            cos[i] = Math.cos(Math.PI * 2 / (1 << i));
        }
        ntok();
        int n = ipar();
        int m = ipar();
        int k = ipar();
        int maxSize = 1;
        while (maxSize < n) {
            maxSize *= 2;
        }
        maxSize *= 2;
        aux1 = new Complex[maxSize];
        aux2 = new Complex[maxSize];
        for (int i = 0; i < maxSize; i++) {
            aux1[i] = new Complex();
            aux2[i] = new Complex();
        }
        ntok();
        int[] freq = new int[m];
        for (int i = 0; i < n; i++) {
            int x = ipar()-1;
            freq[x]++;
        }
        ArrayList<long[]> fs = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            if (freq[i] == 0) {
                continue;
            }
            long[] f = new long[freq[i]+1];
            Arrays.fill(f, 1);
            fs.add(f);
        }
        Collections.sort(fs, (a, b) -> Integer.compare(a.length, b.length));
        long[] compress = new long[maxSize];
        int[] lengths = new int[fs.size()];
        int i = 0;
        for (int e = 0; e < fs.size(); e++) {
            lengths[e] = fs.get(e).length;
            for (long x : fs.get(e)) {
                compress[i] = x;
                i++;
            }
        }
        solve(compress, lengths);

        out.println(compress[k]);

        out.flush();
        in.close();
    }

    public void solve(long[] compress, int[] lengths) {
        long[] output = new long[compress.length];
        int n = lengths.length;
        while (n > 1) {
            // out.printf("n = %d%n", n);
            // int offset = 0;
            // for (int i = 0; i < n; i++) {
            //     for (int e = 0; e < lengths[i]; e++) {
            //         out.print(' ');
            //         out.print(compress[offset + e]);
            //     }
            //     offset += lengths[i];
            //     out.println();
            // }
            // out.flush();
            int curr = 0;
            int size = 0;
            for (int i = 0; i < n-1; i += 2) {
                int outSize = merge(compress, curr, lengths[i], curr+lengths[i], lengths[i+1], output, size);
                size += outSize;
                curr += lengths[i] + lengths[i+1];
                lengths[i/2] = outSize;
            }
            if (n % 2 == 1) {
                for (int i = 0; i < lengths[n-1]; i++) {
                    output[size] = compress[curr];
                    size++;
                    curr++;
                }
                lengths[n/2] = lengths[n-1];
            }
            long[] temp = compress;
            compress = output;
            output = temp;
            n = (n+1)/2;
        }
    }

    public int merge(long[] compress, int aStart, int aLen, int bStart, int bLen, long[] output, int outStart) {
        int n = 1;
        while (n < aLen + bLen) {
            n *= 2;
        }
        for (int i = 0; i < aLen; i++) {
            aux1[i].set(compress[aStart + i], 0);
        }
        for (int i = 0; i < bLen; i++) {
            aux2[i].set(compress[bStart + i], 0);
        }
        fft(aux1, false, n);
        fft(aux2, false, n);
        for (int i = 0; i < n; i++) {
            aux1[i].multiply(aux2[i]);
        }
        fft(aux1, true, n);
        for (int i = 0; i < aLen+bLen-1; i++) {
            output[outStart + i] = Math.round(aux1[i].a) % 1009;
        }
        for (int i = 0; i < n; i++) {
            aux1[i].set(0, 0);
        }
        for (int i = 0; i < n; i++) {
            aux2[i].set(0, 0);
        }
        return aLen+bLen-1;
    }

    public void fft(Complex[] f, boolean inverse, int n) {
        int bitCount = 0;
        while (1 << bitCount < n) {
            bitCount++;
        }
        for (int i = 0; i < n; i++) {
            int rev = reverse(i, bitCount);
            if (i < rev) {
                Complex temp = f[i];
                f[i] = f[rev];
                f[rev] = temp;
            }
        }

        Complex temp = new Complex();
        Complex rot = new Complex();
        Complex w = new Complex();
        for (int lenBits = 1; 1 << lenBits <= n; lenBits++) {
            int len = 1 << lenBits;
            rot.set(cos[lenBits], sin[lenBits] * (inverse ? -1 : 1));
            for (int offset = 0; offset < n; offset += len) {
                w.set(1, 0);
                for (int i = 0; i*2 < len; i++) {
                    Complex a = f[offset + i];
                    Complex b = f[offset + i+len/2];
                    temp.set(b);
                    temp.multiply(w);
                    b.set(a);
                    a.add(temp);
                    b.subtract(temp);
                    w.multiply(rot);
                }
            }
        }

        if (inverse) {
            for (Complex c : f) {
                c.a /= n;
                c.b /= n;
            }
        }
    }

    public int reverse(int n, int bitCount) {
        int rev = 0;
        for (int i = 0; i < bitCount; i++) {
            rev *= 2;
            rev += n%2;
            n /= 2;
        }
        return rev;
    }

    private static class Complex {
        double a, b;

        public Complex() {}

        public Complex(double a, double b) {
            this.a = a;
            this.b = b;
        }

        public void multiply(Complex other) {
            double aa = a * other.a - b * other.b;
            double bb = a * other.b + b * other.a;
            a = aa;
            b = bb;
        }

        public void add(Complex other) {
            a += other.a;
            b += other.b;
        }

        public void subtract(Complex other) {
            a -= other.a;
            b -= other.b;
        }

        public void set(Complex other) {
            a = other.a;
            b = other.b;
        }

        public void set(double a, double b) {
            this.a = a;
            this.b = b;
        }
    }

    public void ntok() throws IOException
    {
        tok = new StringTokenizer(in.readLine());
    }

    public int ipar()
    {
        return Integer.parseInt(tok.nextToken());
    }

    public int[] iapar(int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar()
    {
        return Long.parseLong(tok.nextToken());
    }

    public long[] lapar(int n)
    {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar()
    {
        return Double.parseDouble(tok.nextToken());
    }

    public String spar()
    {
        return tok.nextToken();
    }

    public static void main(String[] args) throws IOException
    {
        new F3().go();
    }
}
