8665: BZOJ4665:小w的喜糖
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
废话不多说,反正小w要发喜糖啦!! 小w一共买了n块喜糖,发给了n个人,每个喜糖有一个种类。这时,小w突发奇想,如果这n个人相互交换手中的糖,那会有多少种方案使得每个人手中的糖的种类都与原来不同。 两个方案不同当且仅当,存在一个人,他手中的糖的种类在两个方案中不一样。
输入格式
第一行,一个整数n 接下来n行,每行一个整数,第i个整数Ai表示开始时第i个人手中的糖的种类 对于所有数据,1≤Ai≤k,k<=N,N<=2000
输出格式
一行,一个整数Ans,表示方案数模1000000009
样例输入
6 1 1 2 2 3 3
样例输出
10
提示
没有写明提示
题目来源
没有写明来源