You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ARC108E] Random IS

题目描述

从左到右排列了 $N$ 张椅子，第 $i$ 张的编号为 $a_i$ （保证 $a_i$ 互不相同）。

$\texttt{Snuke}$ 想要标记一些椅子并把剩下的丢掉，一开始所有椅子都没有被标记。我们称一种标记方案是好的，当且仅当其标号递增。即，若标记的编号为 $i_1<i_2<\cdots<i_k$，则有 $a_{i_1}<a_{i_2}<\cdots<a_{i_k}$。

$\texttt{Snuke}$ 将重复一下操作来标记椅子：

1. 称 $x$ 是不错的当且仅当把 $x$ 加入后标记方案仍是好的，记其数量为 $k$；

2. 若 $k=0$ 结束操作，否则均匀随机选择一个标记并继续操作 $1$；

求最终标记个数的期望，将结果对 $10^9+7$ 进行有理数取模后进行输出。一个有理数 $a/b$ 对 $M$ 取模的计算方式为找到一个 $c$ 使得 $a\ \equiv\ b\ \times\ c\ \pmod{M}$ 且 $0\leq c<M$ 。

输入格式

第一行一个整数 $N$ ，第二行 $N$ 个整数 $a_i$ 。

输出格式

一个实数表示答案。

样例 #1

样例输入 #1

3
3 1 2

样例输出 #1

666666673

样例 #2

样例输入 #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

数据范围

• $1\ \leq\ N\ \leq\ 2000$
• $1\ \leq\ a_i\ \leq\ N$
• 保证 $a_i$ 互不相同

样例解释 1

- 初始没有标记，所以三张椅子随便选。有 $1/3$ 的概率选 $1$ ，此时还可以选 $2$ ，标记数量为 $2$ 。有 $1/3$ 的概率选 $2$ ，此时还可以选 $1$ ，标记数量为 $2$ 。有 $1/3$ 的概率选 $3$ ，此时不能再选，标记数量为 $1$ 。因此期望值为 $\frac{5}{3}$ 。由于 $5\ \equiv\ 3\ \times\ 666666673\ \pmod{10^9+7}$ ，故输出 $666666673$。