#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef long long ll;

const ll MOD = 1e7 + 9;

int main()
{
    int n;
    cin >> n;

    vi vec(n);

    for (int &x : vec) cin >> x;

    sort(vec.begin(), vec.end(), greater<int>());

    ll res = 1;
    ll prev = vec[0], cnt = 0;
    for (ll i=0; i < n; i++) {
        if (vec[i] != prev) {
            res = (res * (cnt + 1LL)) % MOD;
            cnt = 0LL;
        }
        cnt++;
        prev = vec[i];
    }

    cout << res << '\n';

    return 0;
}