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.
mod = 1000000007

def min(a,b):
	if a<b :
		return a
	else:
		return b
		
def Pow(a,b):
	d=1
	t=a
	while b>0:
		if b%2==1:
			d=d*t%mod
		b/=2
		t=t*t%mod
	return d

a=[]
b=[]
vis=[]
sum=0
n,x=map(int,raw_input().split())
a=(map(int,raw_input().split()))
for i in range(len(a)):
	sum += a[i]
for i in range(len(a)):
	b.append(sum-a[i])
	vis.append(0)

Max=sum+10
ans=1
while True:
	Ma = Max
	for i in range(len(b)):
		if vis[i]==0 :
			Ma=min(Ma,b[i])
	if (Ma==0 or Ma==Max):
		break
	ans *= Pow(x,Ma)
	ans %= mod
	num=0
	for i in range(len(b)):
		b[i] -= Ma
		if(b[i]==0):
			num+=1
	sum = sum-Ma
	if (sum<=0 or num%x != 0):
		break
	else :
		p=0
		for i in range(len(b)):
			if(b[i]==0):
				if(p < num/x):
					b[i]=1
					p+=1
				else :
					vis[i]=1

print ans
