废话不多说,反正小 w 要发喜糖啦!! 小 w 一共买了 n 块喜糖,发给了 n 个人,每个喜糖有一个种类。这时,小 w 突发奇想,如果这 n 个人相互交换手中的糖,那会有多少种方案使得每个人手中的糖的种类都与原来不同。 两个方案不同当且仅当,存在一个人,他手中的糖的种类在两个方案中不一样。
第一行,一个整数 n 接下来 n 行,每行一个整数,第 i 个整数 Ai 表示开始时第 i 个人手中的糖的种类。
一行一个整数 Ans,表示方案数模 109+9 的结果。
6
1
1
2
2
3
3
10
对于 100% 的数据,满足 1≤Ai≤k,k≤n,n≤2000。