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 C implements Runnable{
	public static void main (String[] args) {new Thread(null, new C(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		int n = fs.nextInt();
		int x = fs.nextInt();
		long[] a = new long[n];
		for(int i = 0; i < n; i++) a[i] = fs.nextLong();
		long sum = 0;
		for(long i : a) sum += i;
		TreeSet<Long> in = new TreeSet<>();
		HashMap<Long, Long> freq = new HashMap<>();
		for(int i = 0; i < n; i++) {
			a[i] = sum - a[i];
			add(freq, a[i], 1);
			in.add(a[i]);
		}
		long[] pows = new long[100];
		pows[0] = 1;
		for(int i = 1; i < pows.length; i++) {
			try { pows[i] = Math.multiplyExact(pows[i-1], x); }
			catch(Exception e) {
				pows = Arrays.copyOfRange(pows, 0, i);
				break;
			}
		}
		long exp = in.first();
		while(!in.isEmpty()) {
			long check = in.pollFirst();
			long fr = freq.get(check);
			int expo = -1;
			for(int p = pows.length-1; p > 0; p--) {
				if(fr % pows[p] == 0) {
					expo = p;
					break;
				}
			}
			if(expo < 0) {
				exp = check;
				break;
			}
			in.add(check+expo);
			add(freq, check+expo, fr/pows[expo]);
			delete(freq, check, fr);
		}
		exp = Math.min(exp, sum);
		out.println(power(x, exp, (long)1e9+7));
		out.close();
	}
	
	void add(HashMap<Long, Long> map, long i, long fr) {
		if(!map.containsKey(i)) map.put(i, 0L);
		map.put(i, map.get(i) + fr);
	}
	
	void delete(HashMap<Long, Long> map, long i, long fr) {
		long rem = map.get(i) - fr;
		if(rem == 0) map.remove(i);
		else map.put(i, rem);
	}

	long power (long x, long y, long m) {
    	long res = 1;
    	x %= m;
    	while(y > 0) {
    		if(y % 2 == 1) {
    			res = (res * x) % m;
    		}
    		y >>= 1L;
    		x = (x * x) % m;
    	}
    	return res;
    }
	
	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}

	}

}
