Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

* 1 \leq K \leq N \leq 2\times 10^5
* |A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:


N K
A_1 \ldots A_N


Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Examples

Input

4 2
1 2 -3 -4


Output

12


Input

4 3
-1 -2 -3 -4


Output

1000000001


Input

2 1
-1 1000000000


Output

1000000000


Input

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1


Output

999983200
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

mod = 10**9+7
n,k = na()
a = na()
a.sort()

ans = 1

if k == 1:
    print(a[-1])
    exit()

if a[-1] <= 0 and k%2==1:
    for i in range(n-k,n):
        ans = ans*a[i]%mod
    print(ans%mod)
    exit()

s = 0
e = -1

while k > 0:
    if k == 1:
        if a[s] >= a[e]:
            ans = ans*a[s]%mod
        else:
            ans = ans*a[e]%mod
        break
    p = a[s]*a[s+1]
    q = a[e]*a[e-1]
    if p >= q:
        ans = p%mod*ans%mod
        s+=2
    else:
        ans = q%mod*ans%mod
        e-=2
    k-=2

print(ans%mod)