← 返回题目列表

Codeforces · 359/C

C. 素数

中文机器翻译题面 查看原题

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。