只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
4665 - 小w的喜糖
废话不多说，反正小w要发喜糖啦！！ 小w一共买了n块喜糖，发给了n个人，每个喜糖有一个种类。这时，小w突发奇想，如果这n个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。 两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。
Input
第一行，一个整数n 接下来n行，每行一个整数，第i个整数Ai表示开始时第i个人手中的糖的种类 对于所有数据，1≤Ai≤k,k<=N,N<=2000
Output
一行，一个整数Ans，表示方案数模1000000009
Examples
Input
6 1 1 2 2 3 3
Output
10