func_code_string: #include <bits/stdc++.h>   #pragma GCC optimize( O3 )   using namespace std;   int cnt[200005];   int n, m, k;   vector<unsigned long long> polys[200005];   struct cmp {     bool operator()(int a, int b) const {       return polys[a].size() > polys[b].size();     }   };   priority_queue<int, vector<int>, cmp> q;   const int NMAX = 1 << 19;   const double PI = 2 * acos(0.0);   struct FFT {     vector<int> rev;     vector<complex<double> > omega, oinv;     int K, N;     FFT(int k) {       K = k;       N = 1 << k;       rev.resize(N);       omega.resize(N);       oinv.resize(N);       for (int i = 0; i < (N); i++) {         rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (K - 1));         omega[i] = polar(1.0, 2.0 * PI / N * i);         oinv[i] = conj(omega[i]);       }     }     void dft(complex<double>* a, vector<complex<double> >& w) {       for (int i = 0; i < (N); i++)         if (i < rev[i]) swap(a[i], a[rev[i]]);       for (int l = 2; l <= N; l *= 2) {         int m = l / 2;         for (complex<double>* p = a; p != a + N; p += l)           for (int k = 0; k < (m); k++) {             complex<double> t = w[N / l * k] * p[k + m];             p[k + m] = p[k] - t;             p[k] += t;           }       }     }     void fft(complex<double>* a) { dft(a, omega); }     void ifft(complex<double>* a) {       dft(a, oinv);       for (int i = 0; i < (N); i++) a[i] /= N;     }     void conv(complex<double>* a, complex<double>* b) {       fft(a);       fft(b);       for (int i = 0; i < (N); i++) a[i] *= b[i];       ifft(a);     }   };   vector<FFT> fft;   int roundup(int x) {     while (x & (x - 1)) x += x & (-x);     return x;   }   void mul(vector<unsigned long long>& a, vector<unsigned long long>& b) {     int maxsz = a.size() + b.size();     int sz = roundup(maxsz);     a.resize(sz);     b.resize(sz);     static complex<double> aa[1 << 20], bb[1 << 20];     for (int i = 0; i < sz; i++) {       aa[i] = a[i];       bb[i] = b[i];     }     fft[__builtin_ctz(sz) - 1].conv(aa, bb);     a.resize(maxsz);     for (int i = 0; i < maxsz; i++) {       a[i] = real(aa[i]) + 0.5;       a[i] %= 1009;     }   }   int main() {     ios::sync_with_stdio(false);     cin.tie(0);     for (int i = 1; i <= 19; i++) fft.push_back(FFT(i));     cin >> n >> m >> k;     for (int i = 0; i < (n); i++) {       int v;       cin >> v;       cnt[v]++;     }     for (int i = 1; i <= (m); i++) {       if (cnt[i]) {         polys[i].resize(cnt[i] + 1);         fill((polys[i]).begin(), (polys[i]).end(), 1);         q.push(i);       }     }     while (q.size() > 1) {       int a = q.top();       q.pop();       int b = q.top();       q.pop();       mul(polys[a], polys[b]);       q.push(a);     }     vector<unsigned long long>& res = polys[q.top()];     cout << res[k] << endl;     return 0;   }   