题目背景

原创 by：b2019dy、disangan233。

gcd 是一个很臭美的 OIer，他有一些神奇的镜子。

题目描述

gcd 手里一共有 $n$ 个物体，分别称为 $A_1,A_2,A_3\cdots A_n$。这些物体中有元素板也有镜子，元素板上带有若干个元素，镜子一开始不带元素。

一个元素板可以与至多一面镜子相对应，那样的话那面镜子将会带上元素板上的所有元素。镜子可被多个元素板对应，此时它所带的元素数量等于这些元素板的元素数量之和。

一面镜子无法对应其他镜子。

现在告诉你物体总数 $n$ 和每个物体最终所带的元素个数，请问一共有多少种对应情况。

输入格式

第一行：整数 $n$ 表示物品总数。

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

输出格式

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

3
1 2 3

2

5
1 2 2 4 5

8

提示

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