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

#include <bits/stdc++.h>
using namespace std;
int rev[(1 << 18)];
long long p[2] = {998244353, 1004535809};
long long mp[2] = {669690699, -665496394};
long long pw(long long x, long long d, long long P) {
  long long ans = 1;
  while (d) {
    if (d & 1) ans = ans * x % P;
    x = x * x % P;
    d >>= 1;
  }
  return ans;
}
void output(long long *a, int n) {
  for (int i = 0; i < n; i++) cout << a[i] << " ";
  cout << endl;
}
void dft(long long *a, int n, long long P, bool inv = 0) {
  for (int i = 0; i < n; i++) rev[i] = (rev[i >> 1] >> 1) + ((i & 1) * n >> 1);
  for (int i = 0; i < n; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int i = 0, ii = 1; ii < n; i++, ii <<= 1) {
    long long w = pw(3, (P - 1) >> (i + 1), P);
    for (int j = 0; j < n; j += (ii << 1)) {
      long long W = 1;
      for (int k = j; k < j + ii; k++) {
        long long t = a[k];
        (a[k] += W * a[k + ii] % P) %= P;
        a[k + ii] = (t + P - W * a[k + ii] % P) % P;
        W = W * w % P;
      }
    }
  }
  if (inv) {
    for (int i = 1; i < n / 2; i++) swap(a[i], a[n - i]);
    long long in = pw(n, P - 2, P);
    for (int i = 0; i < n; i++) a[i] = a[i] * in % P;
  }
}
int n, m, k, bin[(1 << 18)], num[(1 << 18)];
long long x[(1 << 18)], g[(1 << 18)], invg[(1 << 18)], nowinvg[(1 << 18)],
    gpg[(1 << 18)], gp[(1 << 18)], tmp[(1 << 18)], t1[(1 << 18)], t2[(1 << 18)],
    t3[(1 << 18)];
void mul(long long *a, long long *b, long long *c, int n) {
  for (int i = 0; i < n; i++) {
    t1[i] = a[i];
    t2[i] = b[i];
  }
  dft(t1, n, p[0]);
  dft(t2, n, p[0]);
  for (int i = 0; i < n; i++) t3[i] = t1[i] * t2[i] % p[0];
  dft(t3, n, p[0], 1);
  for (int i = 0; i < n; i++) {
    t1[i] = a[i];
    t2[i] = b[i];
  }
  dft(t1, n, p[1]);
  dft(t2, n, p[1]);
  for (int i = 0; i < n; i++) (t1[i] *= t2[i]) %= p[1];
  dft(t1, n, p[1], 1);
  for (int i = 0; i < n; i++)
    c[i] = (t3[i] * p[0] % 1009 * mp[0] % 1009 +
            t1[i] * (mp[1] % 1009 + 1009) % 1009 * p[1]) %
           1009;
}
int main() {
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    bin[x - 1]++;
  }
  for (int i = 0; i < m; i++) num[bin[i]]++;
  int totnum = 0;
  for (int i = 1; i < n + 1; i++) {
    for (int j = 0; i + j * (i + 1) < ((1 << 18) >> 1); j++)
      (x[i + j * (i + 1)] += (1009 - (i + 1) * num[i] % 1009)) %= 1009;
    totnum++;
  }
  for (int j = 0; j < (1 << 18) >> 1; j++) (x[j] += totnum) %= 1009;
  for (int ii = 1; ii <= n + 1; ii <<= 1)
    if (ii == 1) {
      g[0] = 1;
      invg[0] = 1;
    } else {
      if (ii > 1) {
        mul(g, invg, tmp, ii);
        tmp[0] = 2 - tmp[0];
        for (int i = 1; i < ii >> 1; i++) tmp[i] = (1009 - tmp[i]) % 1009;
        for (int i = ii >> 1; i < ii; i++) tmp[i] = 0;
        mul(invg, tmp, invg, ii);
        for (int i = ii >> 1; i < ii; i++) invg[i] = 0;
      }
      mul(g, invg, tmp, ii << 1);
      tmp[0] = 2 - tmp[0];
      for (int i = 1; i < ii; i++) tmp[i] = (1009 - tmp[i]) % 1009;
      for (int i = ii; i < ii << 1; i++) tmp[i] = 0;
      mul(invg, tmp, nowinvg, ii << 1);
      for (int i = ii; i < ii << 1; i++) nowinvg[i] = 0;
      for (int i = ii; i < ii << 1; i++) invg[i] = 0;
      for (int i = 1; i < ii >> 1; i++) gp[i - 1] = i * g[i];
      mul(gp, nowinvg, gpg, ii << 1);
      tmp[0] = 1;
      for (int i = 1; i < ii; i++)
        tmp[i] = (x[i - 1] + 1009 - gpg[i - 1]) * pw(i, 1009 - 2, 1009) % 1009;
      mul(g, tmp, g, ii << 1);
      for (int i = ii; i < ii << 1; i++) g[i] = 0;
    }
  cout << g[k] << endl;
}
