题目背景

题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。

废话不多说，反正小 w 要发喜糖啦！！

题目描述

小 w 一共买了 $n$ 块喜糖，发给了 $n$ 个人，每个喜糖有一个种类。这时，小 w 突发奇想，如果这 $n$ 个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。

两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。

输入格式

第一行，一个正整数 $n$。

接下来 $n$ 行，每行一个正整数，第 $i$ 个整数 $A_i$ 表示开始时第 $i$ 个人手中的糖的种类。

输出格式

一行一个整数，表示方案数。答案对 $10^9+9$ 取模。

6
1
1
2
2
3
3

10

提示

对于所有数据，$1\leq A_i \leq n \leq 2000$。