题目描述

给定 $N$ 个整数 $A_1,A_2,⋯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≤K≤N≤10^5，-10^5≤A_i≤10^5$。

输出描述

输出一个整数，表示答案。

5 3
-100000
-10000
2
100000
10000

999100009