Maximum Product Selection

Given N integers \(A_1, A_2, \ldots, A_N\), select K numbers such that their product is maximized. Since the product can be very large, output its remainder upon division by \(10^9+9\). The modulo operation is defined in a special way: if \(X < 0\), then \[ X \bmod (10^9+9) = 0 - ((0 - X) \bmod (10^9+9)). \]

Input: The first line contains two integers N and K. The second line contains N integers \(A_1, A_2, \ldots, A_N\).

Output: Output a single integer—the remainder of the maximum product modulo \(10^9+9\), using the modulo definition above.

inputFormat

The first line contains two integers N and K. The second line contains N integers \(A_1, A_2, \ldots, A_N\).

outputFormat

Output a single integer—the maximum product (after selecting exactly K numbers) modulo \(10^9+9\). If the product is negative, output it in the form defined by
\(0 - ((0 - X) \bmod (10^9+9))\).

sample

5 3
1 2 3 4 5

60