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 java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static Input in = new Input(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    static final int MOD = 1_000_000_007;

    public static void main(String[] args) {
        int N = in.nextInt();
        int K = in.nextInt();
        List<Integer> Ap = new ArrayList<>();
        List<Integer> An = new ArrayList<>();
        for (int n = 0; n < N; n++) {
            int A = in.nextInt();
            if (A >= 0) {
                Ap.add(A);
            } else {
                An.add(-A);
            }
        }

        long ans = 1;
        Ap.sort(Comparator.reverseOrder());
        An.sort(Comparator.reverseOrder());
        if (Ap.size() + An.size() == K) {
            for (int a : Ap) {
                ans *= a;
                ans %= MOD;
            }
            for (int a : An) {
                ans *= -a;
                ans %= MOD;
            }
            ans += MOD;
            ans %= MOD;
        } else if (Ap.isEmpty() && K % 2 == 1) {
            An.sort(Comparator.naturalOrder());
            for (int k = 0; k < K; k++) {
                ans *= -An.get(k);
                ans %= MOD;
            }
            ans += MOD;
            ans %= MOD;
        } else {
            if (K % 2 == 1) {
                ans = Ap.remove(0);
                K--;
            }
            int iap = 0;
            int ian = 0;
            int sizeAp = Ap.size();
            int sizeAn = An.size();
            for (K /= 2; K > 0; K--) {
                long ap = -1;
                if (iap + 1 < sizeAp) {
                    ap = Ap.get(iap);
                    ap *= Ap.get(iap + 1);
                }
                long an = -1;
                if (ian + 1 < sizeAn) {
                    an = An.get(ian);
                    an *= An.get(ian + 1);
                }
                if (ap >= an) {
                    iap += 2;
                    ap %= MOD;
                    ans *= ap;
                } else {
                    ian += 2;
                    an %= MOD;
                    ans *= an;
                }
                ans %= MOD;
            }
        }
        ans %= MOD;
        out.println(ans);

        out.flush();
    }

    static class Input {
        private BufferedReader br;
        private String[] buff;
        private int index = 0;

        Input(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
        String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return null;
        }
        String next() {
            while (buff == null || index >= buff.length) {
                buff = nextLine().split(" ");
                index = 0;
            }
            return buff[index++];
        }
        byte nextByte() {
            return Byte.parseByte(next());
        }
        short nextShort() {
            return Short.parseShort(next());
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        float nextFloat() {
            return Float.parseFloat(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
        BigDecimal nextBigDecimal() {
            return new BigDecimal(next());
        }
    }
}

