P10597 BZOJ4665 Xiao w’s Wedding Candy

The problem comes from the original BZOJ. We acknowledge that the statement and original testdata are copyrighted by the original BZOJ or the problem setter who authorized BZOJ to use it. If you are the copyright owner and believe we have infringed your rights, please contact us. --- Enough talk. Anyway, Xiao w is going to hand out wedding candy.

Xiao w bought a total of $n$ pieces of wedding candy and gave them to $n$ people. Each candy has a type. Now Xiao w suddenly has an idea: if these $n$ people exchange the candies in their hands with each other, how many different ways are there such that the type of candy in everyone’s hand is different from what they originally had. Two ways are different if and only if there exists at least one person whose candy type is different between the two ways.

The first line contains a positive integer $n$. The next $n$ lines each contain a positive integer. The $i$-th integer $A_i$ indicates the type of candy in the $i$-th person’s hand at the beginning.

Output one integer in a single line, representing the number of ways. The answer should be taken modulo $10^9+9$.

For all data, $1 \leq A_i \leq n \leq 2000$. Translated by ChatGPT 5