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 on a piece of paper. After Simon led all fractions to a common denominator and summed them up, he got a fraction: , 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 \le n \le 105, 2 \le x \le 109) - the size of the array and the prime number.The second line contains n space-separated integers a1,a2,...,an (0 \le a1 \le a2 \le ... \le an \le 109).

Output Print a single number - the answer to the problem modulo 1000000007 (109+7).

In the first sample . Thus, the answer to the problem is 8.In the second sample, . The answer to the problem is 27, as 351=13 \cdot 27, 729=27 \cdot 27.In the third sample the answer to the problem is 1073741824mod1000000007=73741817.In the fourth sample . Thus, the answer to the problem is 1.