Simon 有一个素数 x 和一个非负整数数组 a1, a2, ..., an。
西蒙非常喜欢分数。今天他在一张纸上写下了数字$$\frac{1}{x^{a_1}} + \frac{1}{x^{a_2}} + \ldots + \frac{1}{x^{a_n}}$$。 Simon 将所有分数引出一个公分母并相加,得到一个分数:$$\text{S}$$,其中数字 t 等于 xa1 + a2 + ... + an。现在西蒙想要减少所得分数。
帮助他,找到数字 s 和 t 的最大公约数。由于 GCD 可能相当大,因此将其打印为除以数字 1000000007 (109 + 7) 后的余数。
输入
第一行包含两个正整数 n 和 x (1 ≤ n ≤ 105, 2 ≤ x ≤ 109) — 数组的大小和素数。
第二行包含 n 个空格分隔的整数 a1, a2, ..., an (0 ≤ a1 ≤ a2 ≤ ... ≤ an ≤ 109)。
输出
打印一个数字——问题的答案以 1000000007 (109 + 7) 为模。
示例
输入 #1
2 2 2 2
输出 #1
8
输入 #2
3 3 1 2 3
输出 #2
27
输入 #3
2 2 29 29
输出 #3
73741817
输入#4
4 5 0 0 0 0
输出#4
1
注意
在第一个样本中 $$\frac{1}{4} + \frac{1}{4} = \frac{4+4}{16} = \frac{8}{16}$$。因此,本题答案为8。
在第二个示例中,$$\frac{1}{3}+\frac{1}{9}+\frac{1}{27}=\frac{243+81+27}{729}=\frac{351}{729}$$。问题的答案是 27,即 351 = 13·27,729 = 27·27。
在第三个示例中,问题的答案是 1073741824 mod 1000000007 = 73741817。
在第四个示例中$$\frac{1}{1}+\frac{1}{1}+\frac{1}{1}+\frac{1}{1}=\frac{4}{1}$$。因此,问题的答案是1。