Maximum Potion Power

Problem Statement

You are given an integer n representing the number of ingredients and an integer k. You are also provided with a list of n integers, each denoting the rarity of an ingredient. Your task is to select exactly k ingredients such that the product of their rarities is maximized. Since this product can be very large, output the result modulo \(10^9+7\).

The product is computed as \(P = (a_{i_1} \times a_{i_2} \times \dots \times a_{i_k}) \mod (10^9+7)\), where \(a_{i_j}\) is the rarity of the chosen ingredients and the selection is made to maximize \(P\).

Note: Exactly k ingredients must be chosen.

inputFormat

Input Format

The input is provided via standard input (stdin) and consists of two lines:

• The first line contains two integers n and k, separated by a space.
• The second line contains n space-separated integers representing the rarities of the ingredients.

outputFormat

Output Format

Output a single integer: the maximum product of any k ingredients' rarities taken modulo \(10^9+7\>.

## sample

5 3
7 4 6 9 3

378