{"problem":{"name":"Erase and Insert","description":{"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)$. Perform the following operation on $Q$ for $i=1,2,\\dots,N$ in this order. *   Rem","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc065_b"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $1 \\le N \\le 5000$\n*   $P$ is a permutation of $(1,2,\\dots,N)$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $\\dots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc065_b","tags":[],"sample_group":[["3\n1 2 3","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)$."],["4\n2 4 1 3","11"],["15\n7 5 14 10 4 2 3 6 8 11 12 1 15 13 9","306264"],["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","33525150"]],"created_at":"2026-03-03 11:01:14"}}