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.*;
import java.util.*;

public class PrimeNumber {
	public static void main(String[] args) throws IOException {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(rd.readLine());
		n = Integer.parseInt(st.nextToken());
		x = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(rd.readLine());
		long[] a = new long[n];
		long sum = 0, max = 0;
		for (int i = 0; i < n; i++) {
			a[i] = Long.parseLong(st.nextToken());
			sum += a[i];
			max = Math.max(max, a[i]);
		}
		for (int i = 0; i < n; i++) {
			updateFrequency(sum - a[i], 1);
		}
		long min = sum - max;
		long deg = min;
		while (true) {
			long m = map.get(deg);
			if (m % x != 0) {
				System.out.println(pow(Math.min(sum, deg)));
				return;
			}
			int pow = 0;
			while (m > 0) {
				long rem = m % x;
				if (rem > 0)
					updateFrequency(deg + pow, rem);
				m /= x;
				pow++;
			}
			deg++;
			while (!map.containsKey(deg))
				deg++;
		}
	}

	static long pow(long p) {
		if (p == 0)
			return 1L;
		long h = pow(p >> 1);
		h = (h * h) % P;
		return p % 2 == 0 ? h : (x * h) % P;
	}

	static void updateFrequency(long deg, long delta) {
		if (map.containsKey(deg))
			map.put(deg, map.get(deg) + delta);
		else
			map.put(deg, delta);

	}

	static HashMap<Long, Long> map = new HashMap<Long, Long>();

	static int x, n;

	static final int P = 1000000007;

}
