{"raw_statement":[{"iden":"problem statement","content":"Given are $N$ integers $A_1,\\ldots,A_N$.\nWe will choose exactly $K$ of these elements. Find the maximum possible product of the chosen elements.\nThen, print the maximum product modulo $(10^9+7)$, using an integer between $0$ and $10^9+6$ (inclusive)."},{"iden":"constraints","content":"*   $1 \\leq K \\leq N \\leq 2\\times 10^5$\n*   $|A_i| \\leq 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"4 2\n1 2 -3 -4"},{"iden":"sample output 1","content":"12\n\nThe possible products of the two chosen elements are $2$, $-3$, $-4$, $-6$, $-8$, and $12$, so the maximum product is $12$."},{"iden":"sample input 2","content":"4 3\n-1 -2 -3 -4"},{"iden":"sample output 2","content":"1000000001\n\nThe possible products of the three chosen elements are $-24$, $-12$, $-8$, and $-6$, so the maximum product is $-6$.\nWe print this value modulo $(10^9+7)$, that is, $1000000001$."},{"iden":"sample input 3","content":"2 1\n-1 1000000000"},{"iden":"sample output 3","content":"1000000000\n\nThe possible products of the one chosen element are $-1$ and $1000000000$, so the maximum product is $1000000000$."},{"iden":"sample input 4","content":"10 10\n1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1"},{"iden":"sample output 4","content":"999983200\n\nBe sure to print the product modulo $(10^9+7)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}