问题陈述

给定一个长度为$N$的整数序列：$A_1, A_2, \cdots, A_N$。

从整数$1, 2, \ldots, A_i$ (对于每个$i (1 \leq i \leq N)$)，通过独立选择$X_i$，以均匀分布的方式随机选择整数，来随机选择一个长度为$N$的整数序列$X$。

计算这个序列$X$的最长递增子序列的期望长度，对$1000000007$取模。

更正式地说，在问题的约束条件下，我们可以证明期望值可以表示为一个分数，即一个不可约分数$\frac{P}{Q}$，并且存在一个整数$R$使得$R \times Q \equiv P \pmod {1000000007}$且$0 \leq R < 1000000007$，所以输出这个整数$R$。

注解

序列$X$的子序列是从$X$中提取一些元素并按照原顺序排列而得到的序列。序列$X$的最长递增子序列是$X$的严格递增子序列中长度最大的序列。

约束条件

• $1 \leq N \leq 6$
• $1 \leq A_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出

对$1000000007$取模后输出期望值。

示例输入1

3
1 2 3

示例输出1

2

令$X$成为下列情况之一，每种情况的概率都是$1/6$：

• $X = (1,1,1)$，此时最长递增子序列的长度为$1$；
• $X = (1,1,2)$，此时最长递增子序列的长度为$2$；
• $X = (1,1,3)$，此时最长递增子序列的长度为$2$；
• $X = (1,2,1)$，此时最长递增子序列的长度为$2$；
• $X = (1,2,2)$，此时最长递增子序列的长度为$2$；
• $X = (1,2,3)$，此时最长递增子序列的长度为$3$。

因此，最长递增子序列的长度的期望值为$(1 + 2 + 2 + 2 + 2 + 3) / 6 \equiv 2 \pmod {1000000007}$。

示例输入2

3
2 1 2

示例输出2

500000005

令$X$成为下列情况之一，每种情况的概率都是$1/4$：

• $X = (1,1,1)$，此时最长递增子序列的长度为$1$；
• $X = (1,1,2)$，此时最长递增子序列的长度为$2$；
• $X = (2,1,1)$，此时最长递增子序列的长度为$1$；
• $X = (2,1,2)$，此时最长递增子序列的长度为$2$。

因此，最长递增子序列的长度的期望值为$(1 + 2 + 1 + 2) / 4 = 3 / 2$。由于$2 \times 500000005 \equiv 3 \pmod {1000000007}$，所以我们应该输出$500000005$。

示例输入3

6
8 6 5 10 9 14

示例输出3

959563502