#P4665. 小w的喜糖

    ID: 3799 传统题 1000ms 128MiB 尝试: 261 已通过: 124 难度: 7 上传者: 标签>CF2200提高容斥原理计数 DP重复元素除重阶乘逆元预处理滚动数组快速幂二项式反演

小w的喜糖

题目描述

废话不多说,反正小 w 要发喜糖啦!!

小 w 一共买了 nn 块喜糖,发给了 nn 个人,每个喜糖有一个种类。

这时,小 w 突发奇想,如果这 nn 个人相互交换手中的糖,那会有多少种方案使得每个人手中的糖的种类都与原来不同。

两个方案不同当且仅当,存在一个人,他手中的糖的种类在两个方案中不一样。

输入格式

第一行,一个整数 nn。

接下来 nn 行,每行一个整数,第 ii 个整数 AiA_i,表示开始时第 ii 个人手中的糖的种类。

输出格式

一行一个整数 AnsAns,表示方案数模 109+910^9+9 的结果。

6
1
1
2
2
3
3
10

数据规模与约定

对于 100%100\% 的数据,满足 1≤Ai≤k1\leq A_i\leq k,k≤nk\leq n,n≤2000n\leq 2000。