该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

海产品价值最大化

题目描述

有 $N$ 种海产品，每种海产品有一个价值 $A_i$（可能为负数，表示亏损）。你需要从中选出 $K$ 种海产品进行销售，使得总价值（乘积）最大。

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

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

输入格式

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

以下 $N$ 行每行一个整数 $A_i$，表示第 $i$ 种海产品的价值。

输出格式

一个整数，表示答案。

输入输出样例 #1

输入 #1

5 3 
-100000   
-10000   
2   
100000  
10000

输出 #1

999100009

输入输出样例 #2

输入 #2

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

输出 #2

-999999829

说明/提示

对于 $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$。