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.
/*
[ ( ^ _ ^ ) ]
*/

// problem: cf/359/C

// package cf.c;

import java.io.*;
import java.util.*;


public class c {
    int INF = (int)1e9;
    long MOD = 1000000007;

    long pow(long a, long n, long mod) {
        long rs = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                rs *= a;
                rs %= mod;
            }
            n >>= 1;
            a *= a;
            a %= mod;
        }
        return rs;
    }

    boolean check(long x, Long[] a, long m) {
        // show("checking for", x, m, a);
        int n = a.length;
        long[] c = new long[n];
        c[0] = 1;
        if(n==1) {
            if(a[0]>=m) return true;
            else return false;
        }
        for(int i=1; i<n; i++) {
            // show("i", a[i], c[i]);
            if(a[i]==a[i-1]) {
                c[i] = c[i-1] + 1;
            } else {
                c[i] = 1;
                if(a[i-1]<m) {
                    long p = a[i-1];
                    long cnt = c[i-1];
                    while(p<a[i] && cnt>0) {
                        if(p<m && cnt%x!=0) return false;
                        p++;
                        cnt /= x;
                    }
                    c[i] += cnt;
                }
            }
        }
        // show("c", c);
        if(a[n-1]<m) {
            long p = a[n-1];
            long cnt = c[n-1];
            while(p<m && cnt>0) {
                if(cnt%x!=0) return false;
                p++;
                cnt = cnt/x;
            }
        }
        // show("ret ture");
        return true;
    }

    void solve(InputReader in, PrintWriter out) throws IOException {
        int n = in.nextInt();
        long x = in.nextLong();
        Long[] a = new Long[n];
        long sum = 0;
        for(int i=0; i<n; i++) {
            a[i] = in.nextLong();
            sum += a[i];
        }
        for(int i=0; i<n; i++) {
            a[i] = sum - a[i];
        }
        Arrays.sort(a);
        long l = 0, h = sum;
        while(l<h) {
            long m = (l+h+1)/2;
            if(check(x, a, m)) {
                l = m;
            } else {
                h = m-1;
            }
        }
        out.println(pow(x, l, MOD));
    }
    

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        int t = 1;//in.nextInt();
        while(t-- >0) {
            new c().solve(in, out);
        }
        out.close();
    }
    
    public static void show(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
    
    static class InputReader {
        static BufferedReader br;
        static StringTokenizer st;
        public InputReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
    }
}