{"problem":{"name":"Urban Planning","description":{"content":"There are $N$ towns numbered $1, 2, \\cdots, N$. Some roads are planned to be built so that each of them connects two distinct towns bidirectionally. Currently, there are no roads connecting towns. In ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"nomura2020_d"},"statements":[{"statement_type":"Markdown","content":"There are $N$ towns numbered $1, 2, \\cdots, N$.\nSome roads are planned to be built so that each of them connects two distinct towns bidirectionally. Currently, there are no roads connecting towns.\nIn the planning of construction, each town chooses one town different from itself and requests the following: roads are built so that the chosen town is reachable from itself using one or more roads.\nThese requests from the towns are represented by an array $P_1, P_2, \\cdots, P_N$. If $P_i = -1$, it means that Town $i$ has not chosen the request; if $1 \\leq P_i \\leq N$, it means that Town $i$ has chosen Town $P_i$.\nLet $K$ be the number of towns $i$ such that $P_i = -1$. There are $(N-1)^K$ ways in which the towns can make the requests. For each way to make requests, find the minimum number of roads needed to meet all the requests, and print the sum of those $(N-1)^K$ numbers, modulo ($10^9+7$).\n\n## Constraints\n\n*   $2 \\leq N \\leq 5000$\n*   $P_i = -1$ or $1 \\leq P_i \\leq N$.\n*   $P_i \\neq i$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $\\cdots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"nomura2020_d","tags":[],"sample_group":[["4\n2 1 -1 3","8\n\nThere are three ways to make requests, as follows:\n\n*   Choose $P_1 = 2, P_2 = 1, P_3 = 1, P_4 = 3$. In this case, at least three roads - for example, $(1,2),(1,3),(3,4)$ - are needed to meet the requests.\n*   Choose $P_1 = 2, P_2 = 1, P_3 = 2, P_4 = 3$. In this case, at least three roads - for example, $(1,2),(1,3),(3,4)$ - are needed to meet the requests.\n*   Choose $P_1 = 2, P_2 = 1, P_3 = 4, P_4 = 3$. In this case, at least two roads - for example, $(1,2),(3,4)$ - are needed to meet the requests.\n\nNote that it is not mandatory to connect Town $i$ and Town $P_i$ directly.\nThe sum of the above numbers is $8$."],["2\n2 1","1\n\nThere may be just one fixed way to make requests."],["10\n2 6 9 -1 6 9 -1 -1 -1 -1","527841"]],"created_at":"2026-03-03 11:01:14"}}