P4871 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$ 个整数表示每一个物品最终的元素数。

输出方案总数对 $10^9+7$ 取模的值。

对于 $20\%$ 的数据，$n\leq 5$。 对于 $50\%$ 的数据，$n\leq 10$。 对于 $100\%$ 的数据，$n\leq 15$。 ### 样例解释 每种方案中，未提及的元素均为元素板，“对应”缩写为 $\to$。 【**样例 1**】 可能的对应方案如下： * 没有镜子。 * $(A_1,A_2)\to A_3$。 答案为：$2$。 【**样例 2**】 可能的对应方案如下： * 没有镜子。 * $(A_2,A_3)\to A_4$。 * $(A_1,A_4)\to A_5$。 * $(A_1,A_2,A_3)\to A_5$。 * $A_2\to A_3$。 * $A_2\to A_3$，$(A_1,A_4)\to A_5$。 * $A_3\to A_2$。 * $A_3\to A_2$，$(A_1,A_4)\to A_5$。 答案为：$8$。