/ 
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
N 脚のイスが左から右に並んでいます。 左から i 番目のイスのIDは a_i です。ここで、a_i がすべて相異なることが保証されます。
すぬけ君は何脚かのイスに印をつけ、印をつけたイス以外を捨てることにしました。はじめ、どのイスにも印はついていません。 印のついたイスたちのIDが左から右に単調増加になっているような印のつけ方を よい印のつけ方 と呼びます。
すぬけ君は以下の手続きに従って印をつけることにしました。
- イス x に新たに印をつけても印のつけ方がよい印のつけ方のままであるとき、イス x を 良いイス とする。現在の良いイスの脚数を k とする
- 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 を出力せよ。
入力例 1
3 3 1 2
出力例 1
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 です。
入力例 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
Score : 700 points
Problem Statement
There are N isu - chairs in Japanese - arranged from left to right. The i-th chair from the left has the ID number a_i. Here, it is guaranteed that a_i are distinct.
Snuke has decided to mark some of the chairs and throw away the rest. Initially, no chair is marked. We call a choice of marked chairs good when the IDs of the marked chairs are monotonically increasing from left to right.
Snuke has decided to do the following procedure to mark chairs:
- We say a chair x to be nice if (and only if) the choice of marked chairs is still good when x gets marked. Let k be the current number of nice chairs.
- If k=0, remove the unmarked chairs and terminate the procedure. Otherwise, choose one from the k nice chairs with equal probability, mark it, and go back to Step 1.
It can be proved that the expected value of the number of chairs that remain at the end of the procedure is a rational number. Let this value be P/Q, an irreducible fraction. Additionally, let M=10^{9}+7. Then, we can prove that there uniquely exists an integer R between 0 and M-1 (inclusive) such that P \equiv Q \times R \pmod{M}, and that value equals P \times Q^{-1} \pmod{M}, where Q^{-1} is the modular multiplicative inverse of Q. Find R.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2000
- 1 \leq a_i \leq N
- a_i are distinct.
Input
Input is given from Standard Input in the following format:
N a_1 a_2 \cdots a_N
Output
Print R.
Sample Input 1
3 3 1 2
Sample Output 1
666666673
- If Chair 1 (the chair with the ID number 1) gets marked first, two chairs will remain at the end: Chair 1 and 2.
- If Chair 2 gets marked first, two chairs will remain at the end: Chair 1 and 2.
- If Chair 3 gets marked first, one chair will remain at the end: Chair 3.
- Since chairs are chosen with equal probability, the expected value of the number of chairs at the end is \frac{5}{3}. We have 5 \equiv 3 \times 666666673 \pmod{M}, so R=666666673.
Sample Input 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
Sample Output 2
297703424