CF359C.Prime Number

Simon has a prime number x and an array of non-negative integers _a_1, _a_2, ..., a__n.

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 _x__a_1 + _a_2 + ... + a__n. 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).

西蒙有一个质数 $x$ 和一个非负整数数组 $a_1, a_2, \dots, a_n$。

西蒙非常喜欢分数。今天，他在纸上写下了如下数字：

在将所有这些分数通分并求和后，他得到了一个分数：
，
其中数 $t$ 等于 $x^{a_1 + a_2 + \dots + a_n}$。现在西蒙希望约简这个结果分数。

请帮助他求出 $s$ 与 $t$ 的最大公约数（GCD）。由于该 GCD 可能非常大，请输出它对 $1000000007$（即 $10^9 + 7$）取模的结果。

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 _a_1, _a_2, ..., a__n (0 ≤ _a_1 ≤ _a_2 ≤ ... ≤ a__n ≤ 109).

第一行包含两个正整数 $n$ 和 $x$（$1 \leq n \leq 10^5$，$2 \leq x \leq 10^9$）—— 分别表示数组的大小和一个质数。

第二行包含 $n$ 个以空格分隔的整数 $a_1,\,a_2,\,...,\,a_n$（$0 \leq a_1 \leq a_2 \leq\,...\,\leq a_n \leq 10^9$）。

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

输出一个数字——该问题答案对 1000000007（$10^9 + 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·27, 729 = 27·27.

In the third sample the answer to the problem is 1073741824 mod 1000000007 = 73741817.

In the fourth sample . Thus, the answer to the problem is 1.

在第一个样例中，。因此，本题的答案为 8。

在第二个样例中，。本题的答案为 27，因为 $351 = 13 \cdot 27$，$729 = 27 \cdot 27$。

在第三个样例中，本题的答案为 $1073741824 \bmod 1000000007 = 73741817$。

在第四个样例中，。因此，本题的答案为 1。