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.util.*;import java.io.*;import java.math.*;
public class Main
{

    public static void process()throws IOException
    {
        int n=ni();
        long x=nl();
        long[]A=nal(n);
        TreeMap<Long,Long>mp=new TreeMap<>();
        long sum=0;
        for(int i=0;i<n;i++)
            sum+=A[i];
        for(int i=0;i<n;i++)
            mp.put(sum-A[i],mp.getOrDefault(sum-A[i],0l)+1);
        long gcd=0;
        long curr=mp.firstKey()-1;
        while(mp.ceilingKey(curr)!=null)
        {

            curr=mp.ceilingKey(curr);
            long count=mp.get(curr);
            if(count/x>0)
                mp.put(curr+1,mp.getOrDefault(curr+1,0l)+count/x);
            mp.put(curr,count%x);
            gcd=gcd(gcd,count%x);
            if(count%x==0)
                mp.remove(curr);
            curr++;
        }

        // pn(mp);
        // pn(gcd);
        long ans=power(x,Math.min(mp.firstKey(),sum));
        long temp=sum-mp.lastKey();
        while(gcd(gcd,x)>1 && temp>0 && gcd>0)
            {ans=(ans*gcd(x,gcd))%mod;temp--;gcd/=gcd(gcd,x);}
        pn(ans);

    }
    static long mod=(long)1e9+7l;
    static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
        if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
        else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
        int t=1;
        //t=ni();
        while(t-->0) {process();}
        out.flush();out.close();  
    }
        static long power(long x,long y) 
        { 
            long res=1l; 
            x%=mod;         
            while(y>0) 
            { 
                if(y%2==1) 
                    res=(res*x)%mod; 
                y/=2;
                x=(x*x)%mod; 
            } 
            return res%mod; 
        } 
    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
    static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}

/////////////////////////////////////////////////////////////////////////////////////////////////////////

    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
   
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}