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.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Map;
import java.util.TreeMap;
import java.util.StringTokenizer;

public class PrimeNumber {
    final static int MOD = 1000000007;
    
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        
        int N = sc.nextInt();
        int X = sc.nextInt();
        int[] arr = sc.nextIntArray(N);
        
        long sum = 0;
        for (int n : arr) {
            sum += n;
        }
        
        PowTracker pt = new PowTracker();
        for (int n : arr) {
            pt.addNum(sum - n, 1);
        }
        
        long small;
        while (true) {
            Map.Entry<Long, Integer> e = pt.firstEntry();
            if (e.getValue() % X == 0) {
                pt.remove(e.getKey());
                pt.addNum(e.getKey() + 1, e.getValue() / X);
            } else {
                small = e.getKey();
                break;
            }
        }
        
        System.out.println(powX(X, Math.min(sum, small)));
    }
    
    public static long powX(int b, long p) {
        long[] pows = new long[64];
        pows[0] = b;
        for (int i = 1; i < pows.length; i++) {
            pows[i] = (pows[i - 1] * pows[i - 1]) % MOD;
        }
        
        long ans = 1;
        int idx = 0;
        while (p > 0) {
            if (p % 2 == 1) {
                ans = (ans * pows[idx]) % MOD;
            }
            idx++;
            p /= 2;
        }
        return ans;
    }
    
    public static class PowTracker extends TreeMap<Long, Integer> {
        private static final long serialVersionUID = -7905059693618994237L;

        public int getNum(long p) {
            if (this.containsKey(p)) {
                return this.get(p);
            } else {
                return 0;
            }
        }
        
        public void addNum(long p, int n) {
            this.put(p, n + this.getNum(p));
        }
    }

    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        
        int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            String str = "";
            try { str = br.readLine(); }
            catch (IOException e) { e.printStackTrace(); }
            return str;
        }
    }
}