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.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;

public class PrimeNumber
{
    public static void main(String[] args)
    {
        new PrimeNumber(System.in, System.out);
    }

    private static class Solver implements Runnable
    {
        static final long MOD = (long) 1e9 + 7;
        int n;
        long x;
        int[] a;
        InputReader in;
        PrintWriter out;

        void solve() throws IOException
        {
            n = in.nextInt();
            x = in.nextInt();
            a = in.nextIntArray(n);

            long tot = 0;
            long[] diff = new long[n];

            for (int aa : a)
                tot += aa;

            for (int i = 0; i < n; i++)
                diff[i] = tot - a[i];

            Arrays.sort(diff);

            LinkedList<Pair> linkedList = new LinkedList<>();

            for (int i = 0; i < n; i++)
                linkedList.add(new Pair(diff[i], 1));

            long ans = 0;

            while (linkedList.size() > 0)
            {
                Pair pair = linkedList.poll();
                long num = pair.num;
                int freq = pair.freq;

                while (!linkedList.isEmpty() && linkedList.peek().num == num)
                    freq += linkedList.poll().freq;

                if (freq % x == 0)
                    linkedList.addFirst(new Pair(num + 1, (int) (freq / x)));
                else
                {
                    ans = num;

                    break;
                }
            }

            ans = Math.min(ans, tot);
            out.println(CMath.modPower(x, ans, MOD));
        }

        class Pair
        {
            long num;
            int freq;

            public Pair(long num, int freq)
            {
                this.num = num;
                this.freq = freq;
            }

        }

        Solver(InputReader in, PrintWriter out)
        {
            this.in = in;
            this.out = out;
        }

        @Override
        public void run()
        {
            try
            {
                solve();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
        }

    }

    private static class InputReader
    {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        int read()
        {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars)
            {
                curChar = 0;
                try
                {
                    numChars = stream.read(buf);
                }
                catch (IOException e)
                {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        int nextInt()
        {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-')
            {
                sgn = -1;
                c = read();
            }

            int res = 0;

            do
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c & 15;

                c = read();
            } while (!isSpaceChar(c));

            return res * sgn;
        }

        int[] nextIntArray(int arraySize)
        {
            int array[] = new int[arraySize];

            for (int i = 0; i < arraySize; i++)
                array[i] = nextInt();

            return array;
        }

        boolean isSpaceChar(int c)
        {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        void close()
        {
            try
            {
                stream.close();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
        }

        InputReader(InputStream stream)
        {
            this.stream = stream;
        }

    }

    private static class CMath
    {
        static long modPower(long number, long power, long mod)
        {
            if (number == 1 || number == 0 || power == 0)
                return 1;

            number = mod(number, mod);

            if (power == 1)
                return number;

            long square = mod(number * number, mod);

            if (power % 2 == 0)
                return modPower(square, power / 2, mod);
            else
                return mod(modPower(square, power / 2, mod) * number, mod);
        }

        static long mod(long number, long mod)
        {
            return number - (number / mod) * mod;
        }

    }

    private PrimeNumber(InputStream inputStream, OutputStream outputStream)
    {
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Thread thread = new Thread(null, new Solver(in, out), "Solver", 1 << 29);

        try
        {
            thread.start();
            thread.join();
        }
        catch (InterruptedException e)
        {
            e.printStackTrace();
        }

        in.close();
        out.flush();
        out.close();
    }

}
