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())
  A = list(map(int, input().split()))
  MOD = 10**9 + 7
  A = sorted(A)
  if N == K:
      ans0 = 1
      for a in A[0:N]:
          ans0 *= a
          ans0 %= MOD
      print(ans0)
      exit()
  
  if K % 2 == 1 and A[-1] < 0:
      ans0 = 1
      for a in A[N - K : N]:
          ans0 *= a
          ans0 %= MOD
      print(ans0)
      exit()
  
  ansA = 1
  for a in A[0:K]:
      ansA *= a
      ansA %= MOD
  
  A = sorted(A, reverse=True)
  ansB = 1
  for a in A[0:K]:
      ansB *= a
      ansB %= MOD
  
  A = sorted(A, key=lambda x: abs(x), reverse=True)
  ansC = 1
  for a in A[0:K]:
      ansC *= a
      ansC %= MOD
  
  ansD = 1
  for a in A[0 : K - 1]:
      ansD *= a
      ansD %= MOD
  B = sorted(A[K - 1 : N])
  
  if ansD > 0:
      ansD *= B[-1]
  elif ansD < 0:
      ansD *= B[0]
  
  
  if 0 in B:
      ansE = 0
  else:
      ansE = ansD
  # print(ansA, ansB, ansC)
  print(max(ansA, ansB, ansC, ansD, ansE) % 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"}]