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: mod = 10**9 + 7
  n, k = map(int, input().split())
  arr = list(map(int, input().split()))
  arr = sorted(arr, reverse=True, key=lambda x: abs(x))  # 絶対値の順にソートする
  if k == n:  # k=nのときはすべてを掛け合わせるほかない
      ans = 1
      for i in range(n):
          ans *= arr[i]
          ans %= mod
      print(ans)
  else:
      if (
          k % 2 == 1 and max(arr) < 0
      ):  # 答えが負になる場合は絶対値の小さい順にK個掛け合わせる
          ans = 1
          for i in range(k):
              ans *= arr[n - 1 - i]
              ans %= mod
          print(ans)
      else:
          ans = 1
          cnt = 0
          for i in range(k):  # 絶対値の大きい順にK個掛け合わせる
              if arr[i] < 0:  # 負数を掛けた回数を数えておく
                  cnt += 1
              ans *= arr[i]
              ans %= mod
          if cnt % 2 == 0:  # 負数を偶数回掛けていれば答えは非負なのでそのまま出力
              print(ans)
          else:  # そうでなければ調整を行う
              min_plus = -1
              min_minus = 1
              for i in range(
                  k
              ):  # 絶対値の大きい順にK個を見て最小の非負の数・負の数を探す
                  if arr[i] >= 0:
                      min_plus = arr[i]
                  else:
                      min_minus = arr[i]
              max_plus = -1
              max_minus = 1
              for i in range(k, n):  # 残るN-K個を見て最大の非負の数・負の数を探す
                  if arr[i] >= 0 and max_plus == -1:
                      max_plus = arr[i]
                  if arr[i] < 0 and max_minus == 1:
                      max_minus = arr[i]
              if (
                  min_plus == -1
              ):  # もし最小の非負の数がなければ、最小の負の数を取り除くしかない
                  arr.remove(min_minus)
                  ans = 1
                  for i in range(k - 1):
                      ans *= arr[i]
                      ans %= mod
                  ans *= max_plus
                  ans %= mod
              elif (
                  min_minus == 1
              ):  # もし最小の負の数がなければ、最小の非負の数を取り除くしかない
                  arr.remove(min_plus)
                  ans = 1
                  for i in range(k - 1):
                      ans *= arr[i]
                      ans %= mod
                  ans *= max_minus
                  ans %= mod
              elif (
                  min_plus * max_plus >= min_minus * max_minus
              ):  # そうでなければより倍率の大きいほうを選ぶ
                  arr.remove(min_minus)
                  ans = 1
                  for i in range(k - 1):
                      ans *= arr[i]
                      ans %= mod
                  ans *= max_plus
                  ans %= mod
              else:
                  arr.remove(min_plus)
                  ans = 1
                  for i in range(k - 1):
                      ans *= arr[i]
                      ans %= mod
                  ans *= max_minus
                  ans %= 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"}]