乘积最大 ### 题目描述 给定 $N$ 个整数 $A_1, A_2, \cdots A_N$。请你从中选出 $K$ 个数，使其乘积最大。 请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 $10^9+9$ 的余数。 注意，如果 $X<0$，我们定义 $X$ 除以 $10^9+9$ 的余数是负$(-X)$除以 $10^9+9$ 的余数。 即：$0-((0-x) \\% 10^9+9)$。 ### 输入描述 输入格式： 第一行包含两个整数 $N,K$。 以下 $N$ 行每行一个整数 $A_i$。 其中，$1 \leq K \leq N \leq 10^5， -10^5 \leq A_i \leq 10^5$。 ### 输出描述 输出一个整数，表示答案。 ### 输入输出样例 #### 示例 > 输入 ```txt 5 3 -100000 -10000 2 100000 10000 ``` > 输出 ```txt 999100009 ```