let split_string ?(pattern="") = Str.split @@ Str.regexp pattern
let n, k = Scanf.sscanf (read_line ()) "%d %d" @@ fun n k -> (n, k)
let a = read_line () |> split_string ~pattern:" " |> List.map int_of_string

let m_1e9 = int_of_float 1e9 + 7
let ( +^ ) x y = (x + y) mod m_1e9
let ( -^ ) x y = x - y + if x < y then m_1e9 else 0
let ( *^ ) x y = ((x mod m_1e9) * (y mod m_1e9)) mod m_1e9

let rec take res n acc = match (n, acc) with
  | (_, []) | (0, _) -> List.rev res
  | (i, x :: xs) -> take (x :: res) (n - 1) xs
let take = take []

let rec drop n acc = match (n, acc) with
  | (0, acc) -> acc
  | (_, []) -> []
  | (n, x :: xs) -> drop (n - 1) xs

let rec split a b = function
  | [] -> (List.sort compare a |> List.rev, List.sort compare b)
  | x :: rest when x > 0 -> split (x :: a) b rest
  | x :: rest -> split a (x :: b) rest
let plus, minus = split [] [] a

let rec two res = function
  | [] -> res
  | x :: [] -> (x, 1) :: res
  | x :: y :: rest -> two ((x, y) :: res) rest

let solve1 () = 
  let ps = two [] plus in
  let ms = two [] minus in
  let acc = (ps @ ms) |> List.sort (fun (a, b) (c, d) -> abs (c * d) - abs (a * b)) |> List.rev in
  let sum = List.fold_left (fun sum (a, b) -> sum *^ a *^ b) 1 @@ take (k / 2) acc in
  let rec g sum = function
    | [] -> failwith ""
    | (a, _) :: _ when a > 0 -> sum *^ a
    | _ :: rest -> g sum rest 
  in
  if k mod 2 = 1 then g sum (drop (k / 2) acc) else sum

let solve2 () =
  let rec take res n acc = match (n, acc) with
    | (_, []) | (0, _) -> List.rev res
    | (i, x :: xs) -> take (x :: res) (n - 1) xs in
  let take = take [] in
  let a = List.sort (fun a b -> abs a - abs b) a in
  List.fold_left ( *^ ) 1 @@ take k a

let f n = (n + m_1e9) mod m_1e9
  
let () =
  let p_len = List.length plus in
  Printf.printf "%d\n" @@ f @@
  if p_len >= k || (k - p_len) mod 2 = 0 then solve1 () else solve2 ()