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: N = int(input())
  P_list = list(map(int, input().split()))
  
  
  class UnionFind:
      def __init__(self, n):
          self.groups = [g for g in range(n)]
  
      def get_root(self, node):
          parent = self.groups[node]
          if parent == node:
              return parent
          else:
              root = parent
              parent = self.groups[parent]
              while root != parent:
                  root = parent
                  parent = self.groups[parent]
  
              while node != root:
                  tmp = self.groups[node]
                  self.groups[node] = root
                  node = tmp
  
              return root
  
      def set_root(self, node, root):
          parent = self.groups[node]
          while parent != root:
              self.groups[node] = root
              node = parent
              parent = self.groups[node]
  
      def combine(self, i1, i2):
          self.set_root(i2, self.get_root(i1))
  
      def in_same_group(self, i1, i2):
          return self.get_root(i1) == self.get_root(i2)
  
      def to_counts(self):
          table = [None] * len(self.groups)
          for i in range(len(self.groups)):
              g = self.get_root(i)
              if table[g] != None:
                  table[g] += 1
              else:
                  table[g] = 1
  
          for i in range(len(self.groups)):
              table[i] = table[self.get_root(i)]
  
          return table
  
      def to_list_list(self):
          table = [[] for _ in range(len(self.groups))]
          for i in range(len(self.groups)):
              g = self.get_root(i)
              if table[g] != None:
                  table[g].append(i)
              else:
                  table[g] = [i]
  
          for i in range(len(self.groups)):
              table[i] = table[self.get_root(i)]
  
          return table
  
      def to_dic(self):
          table = {}
          for i in range(len(self.groups)):
              g = self.get_root(i)
              if g in table:
                  table[g].append(i)
              else:
                  table[g] = [i]
          return table
  
      def to_list(self):
          table = self.to_dic()
          return [table[g] for g in table]
  
  
  uf = UnionFind(N)
  not_decided = set()
  for i, p in enumerate(P_list):
      if p >= 1:
          p -= 1
          uf.combine(i, p)
      else:
          not_decided.add(i)
  
  total_bridges = 0
  groups = uf.to_list()
  not_decided_counts = []
  for group in groups:
      count = 0
      for i in group:
          if i in not_decided:
              count += 1
      not_decided_counts.append(count)
      total_bridges += len(group) - 1
  
  # print(groups)
  # print(not_decided_counts)
  # print(total_bridges)
  
  M = 10**9 + 7
  
  not_decided_count = len(not_decided)
  total = ((total_bridges + not_decided_count) * pow(N - 1, not_decided_count, M)) % M
  for i in range(len(groups)):
      g1 = groups[i]
      c1 = not_decided_counts[i]
      if c1 > 0:
          l1 = len(g1)
          total = (total - (l1 - 1) * pow(N - 1, not_decided_count - c1, M)) % M
          for j in range(i + 1, len(groups)):
              g2 = groups[j]
              c2 = not_decided_counts[j]
              if c2 > 0:
                  l2 = len(g2)
                  # 				print(not_decided_count, c1, c2)
                  total = (
                      total - (l1 * l2) * pow(N - 1, not_decided_count - c1 - c2, M)
                  ) % M
  
  print(total)
  
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"}]