Description

给定N个整数，可正可负。挑出K个数，让这K个数的乘积最大，输出这个最大乘积模(10^9+7)的结果。

Format

Input

第1行：2个整数，N, K

第2行：N个整数

Output

第1行：1个整数，表示答案

Samples

4 2 
1 2 -3 -4

12

Limitation

1s, 1024KiB for each test case. $1 \le K \le N \le 2 \times 10^5$

$|A_i| \le 10^9$