问题 C: [蓝桥杯 2018 省 B] 乘积最大

给定 $N$ 个整数 $A_1, A_2,\cdots, A_N$。请你从中选出 $K$ 个数，使其乘积最大。  

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 $1000000009$（即 $10^9+9$）的余数。  

注意，如果 $X<0$， 我们定义 $X$ 除以 $1000000009$ 的余数是 $0-((0-x)\bmod 1000000009)$。

第一行包含两个整数 $N$ 和 $K$。

以下 $N$ 行每行一个整数 $A_i$。

一个整数，表示答案。

对于 $40\%$ 的数据，$1\le K\le N\le 100$。

对于 $60\%$ 的数据，$1\le K \le 1000$。

对于 $100\%$ 的数据，$1\le K\le N\le 10^5$，$-10^5\le A_i\le 10^5$。