output_description: Print the maximum product modulo (10^9+7), using an integer between 0 and
  10^9+6 (inclusive).
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N K
      A_1 \ldots A_N
attempt: n, k = map(int, input().split())
  lst = list(map(int, input().split()))
  res = 10**9 + 7
  
  plst = sorted([x for x in lst if x >= 0], reverse=True)
  nlst = sorted([abs(x) for x in lst if x < 0], reverse=True)
  lenn = len(nlst)
  lenp = len(plst)
  
  
  if lenp == 0 and k % 2 == 1:
      sm = 1
      for i in range(lenn - 1, lenn - k - 1, -1):
          sm *= -nlst[i]
          sm %= res
      print(sm)
      exit()
  
  if lenp == 0 and k % 2 == 0:
      sm = 1
      for i in range(k):
          sm *= nlst[i]
          sm %= res
      print(sm)
      exit()
  
  nlstw = [nlst[2 * i] * nlst[2 * i + 1] for i in range(lenn // 2)]
  lennw = len(nlstw)
  
  if lenn == 0:
      sm = 1
      for i in range(k):
          sm *= plst[i]
          sm %= res
      print(sm)
      exit()
  
  
  ptoken = 0
  ntoken = 0
  nwtoken = 0
  token = 0
  
  
  sm = 1
  while token < k:
  
      if nwtoken == lennw or ptoken + 1 >= lenp:
          break
  
      if token == (k - 1) or plst[ptoken] > nlst[ntoken]:
          sm *= plst[ptoken]
          sm %= res
          ptoken += 1
          token += 1
      else:
          if nlstw[nwtoken] > plst[ptoken] * plst[ptoken + 1]:
              sm *= nlstw[nwtoken]
              sm %= res
              ntoken += 2
              nwtoken += 1
          else:
              sm *= plst[ptoken] * plst[ptoken + 1]
              sm %= res
              ptoken += 2
          token += 2
  else:
      print(sm)
      exit()
  
  if ptoken + 1 >= lenp:
      if (k - token) % 2 == 1:
          sm *= plst[ptoken]
          sm %= res
          token += 1
          while k > token:
              sm *= nlstw[nwtoken]
              sm %= res
              token += 2
              nwtoken += 1
      else:
          while k > token:
              if nwtoken == lennw:
                  break
              sm *= nlstw[nwtoken]
              sm %= res
              token += 2
              nwtoken += 1
          if k != token:
              sm *= plst[ptoken]
              sm %= res
      print(sm)
      exit()
  
  if nwtoken == lennw:
  
      while k > token:
          if ptoken == lenp:
              sm *= nlst[-1]
              token += 1
              continue
          sm *= plst[ptoken]
          sm %= res
          ptoken += 1
          token += 1
      print(sm)
      exit()
  
problem_description: Statement
  
  Given are N integers A_1,\ldots,A_N.
  
  We will choose exactly K of these elements. Find the maximum possible product
  of the chosen elements.
  
  Then, print the maximum product modulo (10^9+7), using an integer between 0
  and 10^9+6 (inclusive).
samples: [{"input": "4 2\n    1 2 -3 -4", "output": "12\n    \n\nThe possible products of the two chosen elements are 2, -3, -4, -6, -8, and\n12, so the maximum product is 12.\n\n* * *"}, {"input": "4 3\n    -1 -2 -3 -4", "output": "1000000001\n    \n\nThe possible products of the three chosen elements are -24, -12, -8, and -6,\nso the maximum product is -6.\n\nWe print this value modulo (10^9+7), that is, 1000000001.\n\n* * *"}, {"input": "2 1\n    -1 1000000000", "output": "1000000000\n    \n\nThe possible products of the one chosen element are -1 and 1000000000, so the\nmaximum product is 1000000000.\n\n* * *"}, {"input": "10 10\n    1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1", "output": "999983200\n    \n\nBe sure to print the product modulo (10^9+7)."}]