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.
input_str = input()
n, x = int(input_str.split()[0]), int(input_str.split()[1])
input_str = input()
a = input_str.split()
s = 0
for i in range(n):
    a[i] = int(a[i])
    #a.append(1000000000)
    s += a[i]

'''
a = []
for i in range(n):
    if i<65536:
        temp = 1
    else:
        temp = 0#random.randint(0, 1000000000)
    s += temp
    a.append(temp)#(557523474, 999999999))'''

sum_a = [s-a[i] for i in range(n)]
minimum = min(sum_a)
res = pow(x, minimum, 1000000007)#FastPow(x, minimum)#x**minimum
sum_xa = 0
s_new = s - minimum
for i in range(n):
    sum_xa += pow(x, s_new - a[i], 1000000007)#FastPow(x, s_new - a[i])

deg = 0
deg_zn = s-minimum
ts = sum_xa
while sum_xa%1==0 and deg_zn:
    sum_xa /= x
    deg += 1 
    deg_zn -= 1
  #  print (deg, sum_xa%1==0)
#if (n, x) == (98304, 2):
#    print (minimum, s, ts, deg)


if deg:
    res *= pow(x, deg-1 if sum_xa%1!=0 else deg)
print (res%1000000007)