output_description: 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).
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      P_1 P_2 \cdots P_N
attempt: import sys
  
  input = lambda: sys.stdin.readline().rstrip()
  sys.setrecursionlimit(max(1000, 10**9))
  write = lambda x: sys.stdout.write(x + "\n")
  
  
  class UnionFindTree:
      def __init__(self, n):
          self.n = n
          self.parent = list(range(n))
          self.size = [1] * n
  
      def root(self, i):
          inter = set()
          while self.parent[i] != i:
              inter.add(i)
              i = self.parent[i]
          r = i
          for i in inter:
              self.parent[i] = r
          return r
  
      def connect(self, i, j):
          if i == j:
              return
          ri = self.root(i)
          rj = self.root(j)
          if ri == rj:
              return
          if self.size[ri] < self.size[rj]:
              self.parent[ri] = rj
              self.size[rj] += self.size[ri]
          else:
              self.parent[rj] = ri
              self.size[ri] += self.size[rj]
  
  
  n = int(input())
  uf = UnionFindTree(n)
  ps = list(map(int, input().split()))
  k = 0
  for i, p in enumerate(ps):
      if p < 0:
          k += 1
          continue
      uf.connect(i, p - 1)
  for i in range(n):
      uf.root(i)
  from collections import Counter, defaultdict
  
  M = 10**9 + 7
  ncount = Counter(uf.parent)
  mcount = defaultdict(int)
  for i, g in enumerate(uf.parent):
      if ps[i] == -1:
          mcount[g] += 1
  
  ans = sum(v - 1 for v in ncount.values())
  ans *= pow(n - 1, k, M)
  
  for kk in ncount.keys():
      ncount[kk] -= mcount[kk]
  
  for kk, mm in mcount.items():
      if mm == 0:
          continue
      nn = ncount[kk]
      ans += (n - mm - nn) * pow(n - 1, k - 1, M) * mm
      ans %= M
  
  nums = [nn + mcount[k] for k, nn in ncount.items() if mcount[k]]
  l = len(nums)
  dp = [[0] * l for _ in range(l)]
  # dp[i][j] : i番目まで使うときの周期j+1の個数
  if nums:
      dp[0][0] = nums[0]
      for i in range(1, l):
          dp[i][0] = dp[i - 1][0] + nums[i]
  
      for i in range(1, l):
          for j in range(1, l):
              dp[i][j] += dp[i - 1][j - 1] * nums[i] * j + dp[i - 1][j]
              dp[i][j] %= M
  
      for j in range(1, l):
          ans -= dp[-1][j] * pow(n - 1, l - j - 1, M)
  
  print(ans)
  
problem_description: Statement
  
  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 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.
  
  These 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.
  
  Let 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).
samples: [{"input": "4\n    2 1 -1 3", "output": "8\n    \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.\n\nThe sum of the above numbers is 8.\n\n* * *"}, {"input": "2\n    2 1", "output": "1\n    \n\nThere may be just one fixed way to make requests.\n\n* * *"}, {"input": "10\n    2 6 9 -1 6 9 -1 -1 -1 -1", "output": "527841"}]