AT_arc108_e.[ARC108E] Random IS

有 $N$ 把椅子从左到右排成一行。第 $i$ 把椅子的 ID 为 $a_i$。这里保证所有 $a_i$ 互不相同。

すぬけ君打算给若干把椅子做上标记，并丢弃没有被标记的椅子。开始时，所有椅子都没有被标记。若标记后的椅子 ID 从左到右单调递增，则称这种标记方式为“好标记方式”。

すぬけ君按照如下流程进行标记：

1. 如果在椅子 $x$ 上新做标记后，标记方式仍然是好标记方式，则称椅子 $x$ 为“好椅子”。当前好椅子的数量为 $k$。
2. 若 $k=0$，则丢弃所有未被标记的椅子，流程结束。否则，从 $k$ 把好椅子中等概率随机选择一把进行标记，然后回到步骤 1。

可以证明，流程结束时剩下的椅子数量的期望值是有理数。设其值为 $P/Q$（既约分数）。又设 $M=10^9+7$。此时，存在唯一的整数 $R$，满足 $0 \leq R < M$ 且 $P \equiv Q \times R \pmod{M}$。可以证明 $R = P \times Q^{-1} \pmod{M}$，其中 $Q^{-1}$ 是 $Q$ 关于 $M$ 的模逆元。请计算 $R$。

输入为一行，格式如下：

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

输出 $R$。

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 2000$
• $1 \leq a_i \leq N$
• 所有 $a_i$ 互不相同。

样例解释 1

• 如果最开始标记了椅子 $1$（ID 为 $1$ 的椅子），最终剩下的椅子为 $1,2$，共 $2$ 把。
• 如果最开始标记了椅子 $2$，最终剩下的椅子为 $1,2$，共 $2$ 把。
• 如果最开始标记了椅子 $3$，最终剩下的椅子为 $3$，共 $1$ 把。
• 椅子被等概率选择，因此最终剩下椅子的期望数量为 $\frac{5}{3}$。由于 $5 \equiv 3 \times 666666673 \pmod{M}$，所以 $R=666666673$。

由 ChatGPT 4.1 翻译