配点 : $700$ 点

問題文

$N$ 脚のイスが左から右に並んでいます。 左から $i$ 番目のイスのIDは $a_i$ です。ここで、$a_i$ がすべて相異なることが保証されます。

すぬけ君は何脚かのイスに印をつけ、印をつけたイス以外を捨てることにしました。はじめ、どのイスにも印はついていません。 印のついたイスたちのIDが左から右に単調増加になっているような印のつけ方を よい印のつけ方 と呼びます。

すぬけ君は以下の手続きに従って印をつけることにしました。

1. イス $x$ に新たに印をつけても印のつけ方がよい印のつけ方のままであるとき、イス $x$ を 良いイス とする。現在の良いイスの脚数を $k$ とする
2. $k=0$ なら印のついていないイスを取り除き手続きを終了する。そうでないなら、$k$ 脚の良いイスから等確率で $1$ つを選んで印をつけ手順 1 へ戻る

手続き終了時に残るイスの脚数の期待値が有理数になることが証明できます。その値を $P/Q$ (既約分数)とします。また $M=10^{9}+7$ とします。このとき、$0$ 以上 $M-1$ 以下の整数 $R$ がただ一つ存在して $P \equiv Q \times R \pmod{M}$ となることが証明でき、その値は $P \times Q^{-1} \pmod{M}$ と等しくなります。ここで、$Q^{-1}$ はモジュラ逆数です。$R$ を求めてください。

制約

• 与えられる入力は全て整数
• $1 \leq N \leq 2000$
• $1 \leq a_i \leq N$
• $a_i$ はすべて相異なる

入力

入力は以下の形式で標準入力から与えられる。

$N$

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

出力

$R$ を出力せよ。

3
3 1 2

666666673

• はじめにイス $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$ です。

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

297703424