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: MOD = 10**9 + 7
  
  N, K = list(map(int, input().split()))
  As = list(map(int, input().split()))
  
  A_pos = [a for a in As if a >= 0]
  A_pos.sort()
  A_pos.reverse()
  
  A_neg = [a for a in As if a < 0]
  A_neg.sort()
  
  ans = 1
  
  pos_used = 0
  neg_used = 0
  
  pos_total = len(A_pos)
  neg_total = len(A_neg)
  
  # 答えが負になるかチェック
  if pos_total < K and (K - pos_total) % 2 == 1:
      # 小さい方から取る
      A_pos.reverse()
      A_neg.reverse()
  
  
  k = K
  # 二つずつペアで見てゆく
  while (pos_used + neg_used) < K:
      # Kが1
      if K == 1:
          if N == 1:
              if pos_total == 1:
                  ans = (ans * A_pos[0]) % MOD
              else:
                  ans = (ans * A_neg[0]) % MOD
          else:
              if pos_total > 0:
                  ans = (ans * A_pos[0]) % MOD
              else:
                  ans = (ans * A_neg[0]) % MOD
          break
  
      # のこり2以上のとき
      if K - (pos_used + neg_used) >= 2:
          # 正の数，負の数とも二つ以上残っているとき
          if (pos_total - pos_used) >= 2 and (neg_total - neg_used) >= 2:
              if (
                  A_neg[neg_used] * A_neg[neg_used + 1]
                  >= A_pos[pos_used] * A_pos[pos_used + 1]
              ):
                  ans = (ans * A_neg[neg_used] * A_neg[neg_used + 1]) % MOD
                  neg_used += 2
              else:
                  ans = (ans * A_pos[pos_used] * A_pos[pos_used + 1]) % MOD
                  pos_used += 2
  
          # もう正の数しか残っていない時
          elif neg_total == neg_used:
              ans = (ans * A_pos[pos_used] * A_pos[pos_used + 1]) % MOD
              pos_used += 2
  
          # もう負の数しか残っていない時
          elif pos_total == pos_used:
              ans = (ans * A_neg[neg_used] * A_neg[neg_used + 1]) % MOD
              neg_used += 2
  
      # のこり一つのとき
      else:
          # もう正の数しか残っていない時
          if neg_total == neg_used:
              ans = (ans * A_pos[pos_used]) % MOD
              pos_used += 1
  
          # もう負の数しか残っていない時
          else:
              ans = (ans * A_neg[neg_used]) % MOD
              neg_used += 1
  
  print(ans)
  
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)."}]