output_description: Print \sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R).
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      u_1 v_1
      u_2 v_2
      :
      u_{N-1} v_{N-1}
attempt: N, K = map(int, input().split())
  mod = 10**9 + 7
  plus = []
  minus = []
  zlen = 0
  for i in map(int, input().split()):
      if i >= 0:
          plus.append(i)
      elif i < 0:
          minus.append(i)
      else:
          zlen += 1
  plen = len(plus)
  mlen = len(minus)
  if K > plen + mlen:
      print(0)
      import sys
  
      sys.exit()
  plus.sort(reverse=True)
  minus.sort()
  pp = [1]
  mp = [1]
  for p in plus:
      pp.append((pp[-1] * p))
  for m in minus:
      mp.append((mp[-1] * (-m)))
  ppm = [1]
  mpm = [1]
  for p in plus[::-1]:
      ppm.append((ppm[-1] * p))
  for m in minus[::-1]:
      mpm.append((mpm[-1] * (-m)))
  ans = -float("inf")
  ans_m = float("inf")
  # kこマイナスから選ぶ
  for k in range(K + 1):
      if mlen < k:
          continue
      if plen < K - k:
          continue
      # 最大を目指す
      if k % 2 == 0:
          tmp = mp[k] * pp[K - k]
          ans = max(ans, tmp)
      # 絶対値最小を目指す
      else:
          tmp = mpm[k] * ppm[K - k]
          ans = min(ans, tmp)
  if ans == -float("inf"):
      ans = -ans_m
  if ans < 0 and zlen > 0:
      print(0)
      import sys
  
      sys.exit()
  print(ans % mod)
  
problem_description: Statement
  
  We have a tree with N vertices and N-1 edges, respectively numbered 1,
  2,\cdots, N and 1, 2, \cdots, N-1. Edge i connects Vertex u_i and v_i.
  
  For integers L, R (1 \leq L \leq R \leq N), let us define a function f(L, R)
  as follows:
  
    * Let S be the set of the vertices numbered L through R. f(L, R) represents the number of connected components in the subgraph formed only from the vertex set S and the edges whose endpoints both belong to S.
  
  Compute \sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R).
samples: [{"input": "3\n    1 3\n    2 3", "output": "7\n    \n\nWe have six possible pairs (L, R) as follows:\n\n  * For L = 1, R = 1, S = \\\\{1\\\\} and we have 1 connected component.\n  * For L = 1, R = 2, S = \\\\{1, 2\\\\} and we have 2 connected components.\n  * For L = 1, R = 3, S = \\\\{1, 2, 3\\\\} and we have 1 connected component, since S contains both endpoints of each of the edges 1, 2.\n  * For L = 2, R = 2, S = \\\\{2\\\\} and we have 1 connected component.\n  * For L = 2, R = 3, S = \\\\{2, 3\\\\} and we have 1 connected component, since S contains both endpoints of Edge 2.\n  * For L = 3, R = 3, S = \\\\{3\\\\} and we have 1 connected component.\n\nThe sum of these is 7.\n\n* * *"}, {"input": "2\n    1 2", "output": "3\n    \n\n* * *"}, {"input": "10\n    5 3\n    5 7\n    8 9\n    1 9\n    9 10\n    8 4\n    7 4\n    6 10\n    7 2", "output": "113"}]