{"raw_statement":[{"iden":"background","content":"题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。\n\n---\n\n废话不多说，反正小 w 要发喜糖啦！！"},{"iden":"statement","content":"小 w 一共买了 $n$ 块喜糖，发给了 $n$ 个人，每个喜糖有一个种类。这时，小 w 突发奇想，如果这 $n$ 个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。\n\n两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。"},{"iden":"input","content":"第一行，一个正整数 $n$。\n\n接下来 $n$ 行，每行一个正整数，第 $i$ 个整数 $A_i$ 表示开始时第 $i$ 个人手中的糖的种类。\n"},{"iden":"output","content":"一行一个整数，表示方案数。答案对 $10^9+9$ 取模。"},{"iden":"note","content":"对于所有数据，$1\\leq A_i \\leq n \\leq 2000$。"}],"translated_statement":null,"sample_group":[["6\n1\n1\n2\n2\n3\n3","10"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}