Oier们的镜子(mirror)

原创By：[b2019dy](https://www.luogu.org/space/show?uid=78488) 、[disangan233](https://www.luogu.org/space/show?uid=72679) $gcd$是一个很臭美的OIer，他有一些神奇的镜子。

$gcd$手里一共有$n$个物体，它们的编号为$A_1,A_2,A_3\cdots A_n$。这些物体中有元素板也有镜子，元素板上带有元素，镜子一开始不带元素。 一个元素板可以与**至多**一面镜子相对应，那样的话那面镜子将会带上元素板上的元素。 一面镜子无法对应其他镜子。 现在告诉你物体总数$n$和每个物体**对应后**所带的元素个数，请问一共有多少种对应情况。

第一行：整数$n$表示物品总数。 第二行：共$n$个整数表示每一个物品最终的元素数。

输出方案总数对$1000000007$取模的值。

3
1 2 3

2

5
1 2 2 4 5

8

对于$20\%$的数据，$n\leq 5$。 对于$50\%$的数据，$n\leq 10$。 对于$100\%$的数据，$n\leq 15$。 ## 样例解释 因为出题人太懒现将解释中的"(其余)全是元素板"缩写为"suki"！"对应"缩写为$\to$ ### 样例1 * suki。 * $A1,A2\to A3$。 #### 答案为：$2$。 ### 样例2 * suki。 * $A2,A3\to A4$，suki。 * $A1,A4\to A5$，suki。 * $A1,A2,A3\to A5$，suki。 * $A2\to A3$，suki。 * $A2\to A3$，$A1,A4$->$A5$。 * $A3\to A2$，suki。 * $A3\to A2$，$A1,A4$->$A5$。 ### 答案为：$8$。