{"raw_statement":[{"iden":"problem statement","content":"You are given a permutation $P$ of $(1,2,\\dots,N)$. There is also a permutation $Q=(1,2,\\dots,N)$ of $(1,2,\\dots,N)$.\nPerform the following operation on $Q$ for $i=1,2,\\dots,N$ in this order.\n\n*   Remove $i$ from $Q$ and insert $i$ into any one position in $Q$.\n\nFind the number, modulo $(10^9+7)$, of ways to perform $N$ operations such that $P$ and $Q$ are equal after all operations."},{"iden":"constraints","content":"*   $1 \\le N \\le 5000$\n*   $P$ is a permutation of $(1,2,\\dots,N)$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $\\dots$ $P_N$"},{"iden":"sample input 1","content":"3\n1 2 3"},{"iden":"sample output 1","content":"5\n\nFor example, the following operations result in $Q = (1,2,3)$.\n\n*   Remove $1$ from $Q=(1,2,3)$ and insert it between $2$ and $3$, making $Q = (2,1,3)$.\n*   Remove $2$ from $Q=(2,1,3)$ and insert it at the end of $Q$, making $Q = (1,3,2)$.\n*   Remove $3$ from $Q=(1,3,2)$ and insert it at the end of $Q$, making $Q = (1,2,3)$.\n\nIncluding this example, five ways to perform operations result in $Q=(1,2,3)$."},{"iden":"sample input 2","content":"4\n2 4 1 3"},{"iden":"sample output 2","content":"11"},{"iden":"sample input 3","content":"15\n7 5 14 10 4 2 3 6 8 11 12 1 15 13 9"},{"iden":"sample output 3","content":"306264"},{"iden":"sample input 4","content":"30\n15 19 13 11 22 27 21 25 1 12 30 28 16 26 10 14 20 2 5 7 23 4 17 6 29 3 18 9 8 24"},{"iden":"sample output 4","content":"33525150"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}