给定N个整数A₁,A₂,...,A_N,请你从中选出K个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整形范围，因此只需要输出乘积除以1000000009的余数。

注意：如果X<0，则定义X除以1000000009的余数是-X除以1000000009的余数，即0-((0-X)%1000000009).

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

以下N 行每行包含一个整数A_i

一个整数，表示答案。

5 3
-100000
-10000
2
100000
10000

999100009

输入样例2

5 3

-100000

-100000

-2

-100000

-100000

输出样例

-999999829