let m = 1000000007
let ( *^ ) x y = (x * y) mod m

let () = Scanf.scanf "%d %d\n" @@ fun n k ->
  let pos, neg =
    List.partition (( <= ) 0) @@
    List.init n @@ fun _ -> Scanf.scanf "%d " @@ fun a -> a in
  let l = List.length pos in
  let l' = List.length neg in
  let pos' = Array.make (l + 1) 1 in
  let pos'' = Array.make (l + 1) 0.  in
  let neg' = Array.make (l' + 1) 1 in
  let neg'' = Array.make (l' + 1) 0.  in
  let neg''' = Array.make (l' + 1) 1 in
  let neg'''' = Array.make (l' + 1) 0.  in
  List.iteri (fun i a ->
    pos'.(i + 1) <- pos'.(i) *^ a;
    pos''.(i + 1) <- pos''.(i) +. log (float_of_int a)) (List.sort (Fun.flip compare) pos);
  List.iteri (fun i a ->
    neg'.(i + 1) <- neg'.(i) *^ (a + m);
    neg''.(i + 1) <- neg''.(i) +. log (float_of_int (~- a))) (List.sort compare neg);
  List.iteri (fun i a ->
    neg'''.(i + 1) <- neg'''.(i) *^ (a + m);
    neg''''.(i + 1) <- neg''''.(i) +. log (float_of_int (~- a))) (List.sort (Fun.flip compare) neg);
  Printf.printf "%d\n" @@
  snd @@
  snd @@
  Array.fold_left max (0, (neg_infinity, 0)) @@
  Array.init (1 + k) @@ fun i ->
    if l < k - i || l' < i then (0, (neg_infinity, 0))
    else if i mod 2 = 1
    then (0, (~-. (pos''.(k - i)) -. neg''''.(i), pos'.(k - i) *^ neg'''.(i)))
    else (1, (pos''.(k - i) +. neg''.(i), pos'.(k - i) *^ neg'.(i)))