题目描述

有 $N$ 把椅子按从左到右排列，每把椅子从左起编号为 $a_i$。保证 $a_i$ 是不同的。

Snuke 决定标记其中一些椅子，并扔掉其他椅子。初始时，没有椅子被标记。如果标记的椅子的编号从左到右是单调递增的，我们称该选择为“好的”。

Snuke 决定按照以下步骤标记椅子：

1. 如果椅子 $x$ 是“好的”，也就是当 $x$ 被标记后选择仍然是好的选择，则将椅子 $x$ 标记为“好的”。设当前好椅子的数量为 $k$。
2. 如果 $k=0$，则移除未标记的椅子并结束过程。否则，从 $k$ 个好椅子中等概率选择一个进行标记，然后返回步骤 1。

可以证明，在过程结束时剩余的椅子数量的期望是一个有理数。设这个期望值为 $P/Q$，其中 $P$ 和 $Q$ 互质。另外，设 $M=10^9+7$。我们可以证明，存在一个介于 $0$ 和 $M-1$（包含）之间的整数 $R$，满足 $P \equiv Q \times R \pmod{M}$，且 $R$ 等于 $P \times Q^{-1} \pmod{M}$，其中 $Q^{-1}$ 是 $Q$ 的模逆元。求 $R$ 的值。

约束条件

• 输入中的所有值都是整数。
• $1 \leq N \leq 2000$
• $1 \leq a_i \leq N$
• $a_i$ 是不同的。

输入

从标准输入读入输入数据的格式如下：

$N$ $a_1$ $a_2$ $\cdots$ $a_N$

输出

输出 $R$。

示例输入 1

3
3 1 2

示例输出 1

666666673

• 如果首先标记椅子 $1$（编号为 $1$ 的椅子），则最后剩下两把椅子：椅子 $1$ 和椅子 $2$。
• 如果首先标记椅子 $2$，则最后剩下两把椅子：椅子 $1$ 和椅子 $2$。
• 如果首先标记椅子 $3$，则最后剩下一把椅子：椅子 $3$。
• 由于选择椅子的概率相等，最后剩余椅子的数量的期望值为 $\frac{5}{3}$。我们有 $5 \equiv 3 \times 666666673 \pmod{M}$，因此 $R=666666673$。

示例输入 2

30
26 16 28 30 23 11 29 18 22 15 20 13 27 9 21 7 5 25 4 19 8 3 1 24 10 14 17 12 2 6

示例输出 2

297703424