{"problem":{"name":"Random IS","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc108_e"},"statements":[{"statement_type":"Markdown","content":"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.\nSnuke 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.\nSnuke has decided to do the following procedure to mark chairs:\n\n1.  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.\n2.  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.\n\nIt 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$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 2000$\n*   $1 \\leq a_i \\leq N$\n*   $a_i$ are distinct.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $\\cdots$ $a_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc108_e","tags":[],"sample_group":[["3\n3 1 2","666666673\n\n*   If Chair $1$ (the chair with the ID number $1$) gets marked first, two chairs will remain at the end: Chair $1$ and $2$.\n*   If Chair $2$ gets marked first, two chairs will remain at the end: Chair $1$ and $2$.\n*   If Chair $3$ gets marked first, one chair will remain at the end: Chair $3$.\n*   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$."],["30\n26 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"]],"created_at":"2026-03-03 11:01:13"}}