F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
Problem 4665. -- 小w的喜糖

4665: 小w的喜糖

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 237  Solved: 138
[Submit][Status][Discuss]

Description

废话不多说,反正小w要发喜糖啦!!
小w一共买了n块喜糖,发给了n个人,每个喜糖有一个种类。这时,小w突发奇想,如果这n个人相互交换手中的糖,那会有多少种方案使得每个人手中的糖的种类都与原来不同。
两个方案不同当且仅当,存在一个人,他手中的糖的种类在两个方案中不一样。

Input

第一行,一个整数n
接下来n行,每行一个整数,第i个整数Ai表示开始时第i个人手中的糖的种类
对于所有数据,1≤Ai≤k,k<=N,N<=2000

Output

一行,一个整数Ans,表示方案数模1000000009

Sample Input

6
1
1
2
2
3
3

Sample Output

10

HINT

Source

[Submit][Status][Discuss]

HOME Back