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.util.ArrayList;

import java.util.Collections;
import java.util.Scanner;

public class PrimeNumber 
{
	static int mod=1000000007;

	public static void main(String[] args) 
	 {
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int x=scan.nextInt();
		long []power=new long[n];
		ArrayList<Long>doa=new ArrayList<>();
		long sum=0;
		for(int i=0;i<n;i++) 
		  {
		 	power[i]=scan.nextInt();
		 	sum+=power[i];
		  }
		for(int i=0;i<n;i++) 
		  {
			doa.add(sum-power[i]);
		  }
		doa.sort(Collections.reverseOrder());
		while(true) 
		{
			
			//if(doa.size()>0)
			{
			long v=doa.get(doa.size()-1);
			int cnt=0;
			while(doa.size()>0&&doa.get(doa.size()-1)==v) 
				{
				 cnt++;
				 doa.remove(doa.size()-1);
				}
			if(cnt%x!=0) 
			 {
				v=min(v,sum);
				System.out.println(fExpo(x,v));
				break;
			 }
			else 
			 {
				cnt/=x;
				for(int i=0;i<cnt;i++) 
				{
				  doa.add(v+1);
				}
			 }
			}
		}
		}
	 
	static long min(long a,long b)
	{
		if(a<b) 
		{
			return a;
		}
		else 
		{
			return b;
		}
	}
	static long fExpo(long base,long power) 
	{
		long res=1;
		base=base%mod;
		while(power>0) 
		{
			if(power%2!=0) 
			 {
				res=(res*base)%mod;
				power-=1;
			 }
			else 
			{
				base=(base*base)%mod;
				power/=2;
			}
		}
		return res;
	}
}

