Problem Description

Given $N$ integers $A_1, A_2,\cdots, A_N$. Please choose $K$ numbers from them so that their product is maximized.

Output the maximum product. Since the product may exceed the integer range, you only need to output the remainder of the product modulo $1000000009$ (i.e., $10^9+9$).

Note that if $X<0$, we define the remainder of $X$ divided by $1000000009$ as $0-((0-x)\bmod 1000000009)$.

Input Format

The first line contains two integers $N$ and $K$.

In the next $N$ lines, each line contains one integer $A_i$.

Output Format

Output one integer, the answer.

5 3 
-100000   
-10000   
2   
100000  
10000

999100009

5 3 
-100000   
-100000   
-2   
-100000  
-100000

-999999829

Hint

For $40\%$ of the testdata, $1\le K\le N\le 100$.

For $60\%$ of the testdata, $1\le K \le 1000$.

For $100\%$ of the testdata, $1\le K\le N\le 10^5$, $-10^5\le A_i\le 10^5$.

Translated by ChatGPT 5