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.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class B {
	
	static final int mod = (int)1e9 + 7;
	public static void main(String[] args) throws IOException 
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int n = sc.nextInt(), x = sc.nextInt(), a[] = new int[n];
		long sum = 0;
		for(int i = 0; i < n; ++i)
			sum += a[i] = sc.nextInt();
		
		PriorityQueue<Long> pq = new PriorityQueue<Long>();
		for(int i = 0; i < n; ++i)
			pq.add(sum - a[i]);
		long y = 0;
		while(!pq.isEmpty())
		{
			long z = pq.remove() - y, m = 1;
			while(!pq.isEmpty() && pq.peek() - y == z)
			{
				++m;
				pq.remove();
			}
			y += z;
			if(m % x != 0)
				break;
			long zz = 0;
			while(m % x == 0)
			{	
				++zz;
				m /= x;
			}
			while(m--> 0)
				pq.add(zz + y);
		}
		out.println(modPow(x, Math.min(sum, y)));
		out.flush();
		out.close();
	}
		
	static int modPow(long p, long e)
	{
		long res = 1;
		p %= mod;
		while(e > 0)
		{
			if((e & 1) == 1)
				res = res * p % mod;
			p = p * p % mod;
			e >>= 1;
		}
		return (int)res;
	}

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public Scanner(FileReader r){	br = new BufferedReader(r);}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}

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

		public String nextLine() throws IOException {return br.readLine();}

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

		public boolean ready() throws IOException {return br.ready();}


	}
}