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.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.io.*;
import java.math.*;
import java.text.*; 
import java.util.*;

/*
br = new BufferedReader(new FileReader("input.txt"));
pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
br = new BufferedReader(new InputStreamReader(System.in));
pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
 */

public class Main {
  private static BufferedReader br;
  private static StringTokenizer st;
  private static PrintWriter pw;

  public static void main(String[] args) throws IOException {
    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    //int qq = 1;
    int qq = Integer.MAX_VALUE;
    //int qq = readInt();
    for(int casenum = 1; casenum <= qq; casenum++)  {
      int n = readInt();
      int x = readInt();
      long pow = x;
      Set<Long> set = new HashSet<Long>();
      while(pow <= n) {
        set.add(pow);
        pow *= x;
      }
      long[] nums = new long[n];
      long sum = 0;
      for(int i = 0; i < n; i++) {
        nums[i] = readInt();
        sum += nums[i];
      }
      int num = 0;
      long extras = 0;
      for(int i = n-1; i >= 0;) {
        int j = i;
        while(j >= 0 && nums[j] == nums[i]) {
          j--;
          num++;
        }
        if(j == -1) {
          while(num%x == 0) {
            extras++;
            num /= x;
          }
        }
        else {
          long diff = nums[i] - nums[j];
          while(diff > 0) {
            if(num % x != 0) {
              break;
            }
            extras++;
            num /= x;
            diff--;
          }
          if(diff != 0) {
            break;
          }
        }
        i = j;
      }
      pw.println(modpow(x, Math.min(sum, sum - nums[n-1] + extras), 1000000007));
    }
    pw.close();
  }

  public static long modpow(long b, long e, long m) {
    long r = 1;
    while(e > 0) {
      if(e%2==1) {
        r*=b;
        r%=m;
      }
      b*=b;
      b%=m;
      e/=2;
    }
    return r;
  }
  
  private static void exitImmediately() {
    pw.close();
    System.exit(0);
  }

  private static long readLong() throws IOException {
    return Long.parseLong(nextToken());
  }

  private static double readDouble() throws IOException {
    return Double.parseDouble(nextToken());
  }

  private static int readInt() throws IOException {
    return Integer.parseInt(nextToken());
  }

  private static String nextToken() throws IOException  {
    while(st == null || !st.hasMoreTokens())  {
      if(!br.ready()) {
        exitImmediately();
      }
      st = new StringTokenizer(br.readLine().trim());
    }
    return st.nextToken();
  }
}


