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: import numpy as np
  
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  mod = int(1e9 + 7)
  
  A = np.array(sorted(A, reverse=True, key=lambda x: abs(x)))
  if sum(np.sign(A)) == -N and K % 2 == 1:
      A = sorted(A, reverse=True)
  last_p = 0
  last_m = 0
  eliminate_m = 0
  eliminate_p = 0
  add_m = 0
  add_p = 0
  ans = 1
  for i in range(N):
      if i < K:
          ans = (ans * A[i]) % mod
          if A[i] > 0:
              last_p = i
          else:
              last_m = i
      else:
          if A[i] > 0 and eliminate_m == 0:
              eliminate_m = A[last_p] * A[i]
              add_p = A[i]
          elif A[i] < 0 and eliminate_p == 0:
              eliminate_p = A[last_m] * A[i]
              add_m = A[i]
      if i == K - 1:
          if ans > 0:
              break
  if eliminate_p > 0 or eliminate_m > 0:
      if eliminate_m > eliminate_p:
          ans = (ans * pow(A[last_m], mod - 2)) % mod
          ans = (ans * add_p) % mod
      else:
          ans = (ans * pow(A[last_p], mod - 2)) % mod
          ans = (ans * add_m) % mod
  
  print(ans)
  
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"}]