import sys

def mod_inv(a, b, s0 = 1, s1 = 0): 
    if b == 0:
        return s0
    return mod_inv(b, a % b, s1, s0 - s1*(a // b));

n = int(sys.stdin.readline())
p = 1000000009
a = sorted([int(x) for x in sys.stdin.readline().split()])
inv = [0]*(n+1)

# Precompute modular inverses for convenience.
for i in range(1, n+1):
    inv[i] = (mod_inv(i, p) + p) % p


# perm[k][l] contains the number of distinct permutations of 
# a[k], ..., a[l-1].

perm = [[0]*(n+1) for _ in range(n+1)]
for k in range(n+1):
    perm[k][k] = 1
    ct = 0

    for l in range(k+1, n+1):

        if l > k + 1 and a[l-2] == a[l-1]:
            ct += 1
        else:
            ct = 1

        perm[k][l] = (perm[k][l - 1]*(l-k) % p * inv[ct]) % p

eus = [0]*(n+1)
eus[0] = 1;

for k in range(1, n+1):
    # A k element sequence which is not entirely unsorted has a first
    # sorted element, and we count them by the position of that first
    # element. The elements before that are entirely unsorted, and the
    # elements after are in any order.
    #
    # Then we just subtract the unentirely unsorted sequences from all
    # sequences we can make out of the first k elements, to get the
    # entirely unsorted ones.

    eus[k] = perm[0][k]
    for i in range(k):
        eus[k] -= (eus[i] * perm[i+1][k]) % p
        eus[k] %= p
        if eus[k] < 0:
            eus[k] += p;

print(eus[n])