题目背景

原创By：b2019dy 、disangan233

$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$。