/*! path: src/contest/atcoder/abc173/e.ts */!function(t){var e={};function n(r){if(e[r])return e[r].exports;var o=e[r]={i:r,l:!1,exports:{}};return t[r].call(o.exports,o,o.exports,n),o.l=!0,o.exports}n.m=t,n.c=e,n.d=function(t,e,r){n.o(t,e)||Object.defineProperty(t,e,{enumerable:!0,get:r})},n.r=function(t){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(t,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(t,"__esModule",{value:!0})},n.t=function(t,e){if(1&e&&(t=n(t)),8&e)return t;if(4&e&&"object"==typeof t&&t&&t.__esModule)return t;var r=Object.create(null);if(n.r(r),Object.defineProperty(r,"default",{enumerable:!0,value:t}),2&e&&"string"!=typeof t)for(var o in t)n.d(r,o,function(e){return t[e]}.bind(null,o));return r},n.n=function(t){var e=t&&t.__esModule?function(){return t.default}:function(){return t};return n.d(e,"a",e),e},n.o=function(t,e){return Object.prototype.hasOwnProperty.call(t,e)},n.p="",n(n.s=0)}([function(t,e,n){"use strict";(function(t){var r=this&&this.__importDefault||function(t){return t&&t.__esModule?t:{default:t}};Object.defineProperty(e,"__esModule",{value:!0}),e.main=e.solve=e.calcMulti=void 0;const o=r(n(2)),l=n(3);function u(t){let e=1;for(const n of t)e=e*n%1000000007;return e<0?1000000007+e:e}function i({N:t,K:e,A:n}){if(t===e)return u(n);let r=!0;for(let e=0;e<t;e++)n[e]>=0&&(r=!1);if(r&&e%2==1)return n.sort((t,e)=>Math.abs(t)-Math.abs(e)),u(n.slice(0,e));n.sort((t,e)=>Math.abs(e)-Math.abs(t));let o=!1;for(let t=0;t<e;t++)n[t]<0&&(o=!o);if(!o)return u(n.slice(0,e));let l=null,i=null;for(let t=e-1;t>=0;t--)null!=l&&n[t]>=0&&(l=t),null!=i&&n[t]<0&&(i=t);let c=null,f=null;for(let r=e;r<t;r++)null!=c&&n[r]>=0&&(c=r),null!=f&&n[r]<0&&(f=r);if(null===l||null===f){const t=n[i];n[i]=n[c],n[c]=t}else if(null===i||null===c){const t=n[l];n[l]=n[f],n[f]=t}else{if(BigInt(n[f])*BigInt(n[i])<BigInt(n[c])*BigInt(n[l])){const t=n[i];n[i]=n[c],n[c]=t}else{const t=n[l];n[l]=n[f],n[f]=t}}return u(n.slice(0,e))}function c(t){const e=l.getNextInt(t),n=e(),r=e(),o=[];for(let t=0;t<n;t++)o[t]=e();const u=i({N:n,K:r,A:o});console.log(u)}if(e.calcMulti=u,e.solve=i,e.main=c,n.c[n.s]===t){c(o.default.readFileSync("/dev/stdin","utf8"))}}).call(this,n(1)(t))},function(t,e){t.exports=function(t){return t.webpackPolyfill||(t.deprecate=function(){},t.paths=[],t.children||(t.children=[]),Object.defineProperty(t,"loaded",{enumerable:!0,get:function(){return t.l}}),Object.defineProperty(t,"id",{enumerable:!0,get:function(){return t.i}}),t.webpackPolyfill=1),t}},function(t,e){t.exports=require("fs")},function(t,e,n){"use strict";function*r(t){const e=t.split(/\s+/);for(const t of e)yield t}Object.defineProperty(e,"__esModule",{value:!0}),e.getNextBigInt=e.getNextInt=e.getNext=e.getIteratorWithParser=e.getIterator=void 0,e.getIterator=r,e.getIteratorWithParser=function*(t,e){const n=t.split(/\s+/);for(const t of n)yield e(t)},e.getNext=function(t){const e=r(t);return()=>e.next().value},e.getNextInt=function(t){const e=r(t);return()=>parseInt(e.next().value)},e.getNextBigInt=function(t){const e=r(t);return()=>BigInt(e.next().value)}}]);