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.math.BigInteger;
import java.util.*;
import java.util.Collections.*;

import static java.util.Collections.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;
import static java.lang.Character.*;

public class Main {

    void run(){
//        boolean oj = true;
//        boolean oj = false;


        Locale.setDefault(Locale.US);
        boolean oj = System.getProperty("ONLINE_JUDGE")!=null;

        String fileName = oj? "castle" : "dwarf";
        try {
            if( oj ){
                br = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            }
            else{
                br  = new BufferedReader(new FileReader(fileName+".in" ));
                out = new PrintWriter   (new FileWriter(fileName+".out"));
            }
        } catch (Exception e) {
            MLE();
        }
        long tb = System.currentTimeMillis();
        solve();
//        if( !oj )
//            out.println("TIME: " + (System.currentTimeMillis() - tb) / 1e3) ;
        exit(0);
    }

    BufferedReader br;
    StringTokenizer st;
    PrintWriter out;

    String next(){
        while( st==null || !st.hasMoreElements() ){
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                return null;
            }
        }
        return st.nextToken();
    }
    String nextLine(){
        try {
            return br.readLine();
        } catch (Exception e) {
            return null;
        }
    }
    int nextInt(){ return Integer.parseInt(next()); }
    double nextDouble(){ return Double.parseDouble(next()); }
    long nextLong(){ return Long.parseLong(next()); }

    void exit( int val ){
        out.flush();
        System.exit(val);
    }

    void MLE(){
        int[][] arr = new int[1024*1024][];
        for( int i = 0; i < 1024*1024; ++i )
            arr[i] = new int[1024*1024];
    }

    public static void main(String[] args) {
        new Main().run();
    }










    int n;
    long x;
    long [] a;
    long ansPow, sumA;

    TreeMap<Long,Long> tm;

    void add( long pw, long coef ){
        if( !tm.containsKey(pw) )
            tm.put( pw, coef );
        else
            tm.put( pw, tm.get(pw) + coef );
    }

    void solve(){
        ansPow = 0;
        n = nextInt();
        x = nextInt();
        a = new long[n];
        sumA = 0;
        for( int i = 0; i < n; ++i ){
            sumA += a[i] = nextInt();
        }
        sort(a);
        ansPow = sumA - a[n-1];
        tm = new TreeMap<>();
        for( long ai : a )
            add( sumA - ansPow - ai, 1 );



        while(true){
            long pw   = tm.firstKey();
            long coef = tm.pollFirstEntry().getValue();
            if( coef % x == 0 ){
                while( coef % x == 0 ){
                    coef /= x;
                    ++pw;
                }
                add( pw, coef );
            }
            else{
                add( pw, coef );
                break;
            }
        }

        //
        ansPow += tm.firstKey();

        ansPow = min( ansPow, sumA );

        out.println( valueOf(x)
                .modPow(valueOf(ansPow),valueOf((int)1e9+7)) );

    }



}