Simon has a prime number x and an array of non-negative integers a1, a2, ..., an.

Simon loves fractions very much. Today he wrote out number <image> on a piece of paper. After Simon led all fractions to a common denominator and summed them up, he got a fraction: <image>, where number t equals xa1 + a2 + ... + an. Now Simon wants to reduce the resulting fraction. 

Help him, find the greatest common divisor of numbers s and t. As GCD can be rather large, print it as a remainder after dividing it by number 1000000007 (109 + 7).

Input

The first line contains two positive integers n and x (1 ≤ n ≤ 105, 2 ≤ x ≤ 109) — the size of the array and the prime number.

The second line contains n space-separated integers a1, a2, ..., an (0 ≤ a1 ≤ a2 ≤ ... ≤ an ≤ 109). 

Output

Print a single number — the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

2 2
2 2


Output

8


Input

3 3
1 2 3


Output

27


Input

2 2
29 29


Output

73741817


Input

4 5
0 0 0 0


Output

1

Note

In the first sample <image>. Thus, the answer to the problem is 8.

In the second sample, <image>. The answer to the problem is 27, as 351 = 13·27, 729 = 27·27.

In the third sample the answer to the problem is 1073741824 mod 1000000007 = 73741817.

In the fourth sample <image>. Thus, the answer to the problem is 1.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.AbstractCollection;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.PriorityQueue;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.File;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Atharva Nagarkar
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        JoltyScanner in = new JoltyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CPrimeNumber solver = new CPrimeNumber();
        solver.solve(1, in, out);
        out.close();
    }

    static class CPrimeNumber {
        public void solve(int testNumber, JoltyScanner in, PrintWriter out) {
            final int mod = (int) 1e9 + 7;
            int n = in.nextInt();
            long x = in.nextInt();
            int[] a = new int[n];
            long tsum = 0;
            for (int i = 0; i < n; ++i) tsum += (a[i] = in.nextInt());
            PriorityQueue<Long> sums = new PriorityQueue<>(Long::compare);
            for (int i = 0; i < n; ++i) sums.add(tsum - a[i]);
            long expo = -1;
            while (!sums.isEmpty()) {
                int count = 1;
                expo = sums.poll();
                while (!sums.isEmpty() && sums.peek() == expo) {
                    ++count;
                    sums.poll();
                }
                if (count % x != 0) {
                    break;
                }
                for (int i = 0; i < count / x; ++i) {
                    sums.add(expo + 1);
                }
            }
            if (expo > tsum) expo = tsum;
            long ans = 1;
            while (expo > 0) {
                if (expo % 2 == 0) {
                    expo /= 2;
                    x = (x * x) % mod;
                } else {
                    expo--;
                    ans = (ans * x) % mod;
                }
            }
            out.println(ans);
        }

    }

    static class JoltyScanner {
        public int BS = 1 << 16;
        public char NC = (char) 0;
        public byte[] buf = new byte[BS];
        public int bId = 0;
        public int size = 0;
        public char c = NC;
        public double num = 1;
        public BufferedInputStream in;

        public JoltyScanner(InputStream is) {
            in = new BufferedInputStream(is, BS);
        }

        public JoltyScanner(String s) throws FileNotFoundException {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        }

        public char nextChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            num = 1;
            boolean neg = false;
            if (c == NC) c = nextChar();
            for (; (c < '0' || c > '9'); c = nextChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = nextChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                num *= 10;
            }
            return neg ? -res : res;
        }

    }
}

