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 PrimeNumber {
    public static long mod = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        long x = Long.parseLong(st.nextToken());
        long[] a = new long[n];
        st = new StringTokenizer(f.readLine());
        long sum = 0;
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
            sum += a[i];
        }

//      int count = 1;
//      for (int i = 1; i < n; i++) 
//          if (a[i]==a[i-1]) {
//              count++;
//              if (count == x) {
//                  a[(int)(i-x+1)]--;
//                  for (int j = i+1; j < n; j++)
//                      a[(int)(j-x+1)] = a[j];
//                  n -= (x-1);
//                  i -= (x-1);
//                  while (i > 0 && a[i-1] == a[i])
//                      i--;
//                  count = 1;
//              }
//          }
//          else
//              count = 1;
        
        long m = a[n-1];
        int i = n-1;
        long count = 1;
        while (i > 0 && a[i-1] == m) {
            i--;
            count++;
        }
        if (count % x == 0)
            count /= x;
        else
            count = 0;
        while (count > 0) {
            m--;
            while (i > 0 && a[i-1] == m) {
                i--;
                count++;
            }
            if (count % x == 0)
                count /= x;
            else
                count = 0;
        }
        
        long max = Math.max(0,m);
        System.out.println(pow(x,sum-max));
    }
    
    public static long pow(long a, long n) {
        if (n == 0)
            return 1;
        long x = pow(a,n/2);
        x = (x*x) % mod;
        if (n%2 == 1)
            x = (x*a) % mod;
        return x;
    }
}
