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 final class prime_number
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static long mod=(long)(1e9+7);
	static Map<Long,Integer> m1=new TreeMap<>();
	static Map<Long,Long> m2=new HashMap<>();
	
	static long pow(long a,long b)
	{
		long x=1,y=a%mod;
		while(b>0)
		{
			if(b%2==1)
			{
				x=(x*y)%mod;
			}
			y=(y*y)%mod;b=b/2;
		}
		return x;
	}
	
	static void put(long idx,int val)
	{
		if(m1.get(idx)==null)
			m1.put(idx,val);
		else
			m1.put(idx,m1.get(idx)+val);
	}
	
	static void put2(long idx)
	{
		m2.put(idx,1L);
	}
	
	static int get(long idx)
	{
		return (m1.get(idx)==null?0:m1.get(idx));
	}
	
	static boolean get2(long idx)
	{
		return (m2.get(idx)!=null);
	}
	
    public static void main(String args[]) throws Exception
    {
		int n=sc.nextInt(),x=sc.nextInt();long[] a=new long[n];long sum=0;ArrayDeque<Pair> ad=new ArrayDeque<>();
		for(int i=0;i<n;i++)
		{
			a[i]=sc.nextInt();sum+=a[i];
		}
		for(int i=0;i<n;i++)
		{
			a[i]=sum-a[i];put(a[i],1);
		}
		long min=Long.MAX_VALUE;
		for(Map.Entry<Long,Integer> en:m1.entrySet())
		{
			ad.addLast(new Pair(en.getKey(),0));put2(en.getKey());
		}
		while(ad.size()>0)
		{
			Pair curr=ad.removeFirst();curr.val+=get(curr.idx);
			if(curr.val<x)
			{
				min=curr.idx;break;
			}
			else
			{
				if(curr.val%x!=0)
				{
					min=curr.idx;break;
				}
				else if(get2(curr.idx+1))
				{
					put(curr.idx+1,curr.val/x);
				}
				else
				{
					ad.addFirst(new Pair(curr.idx+1,curr.val/x));
				}
			}
		}
		out.println(pow(x,Math.min(min,sum)));out.close();
    }
}
class Pair
{
	long idx;int val;
	public Pair(long idx,int val)
	{
		this.idx=idx;this.val=val;
	}
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}