Bờm có một số nguyên tố \(x\) và một mảng các số nguyên không âm \(a_{1},\ a_{2},\ \ldots,\ a_{n}\).

Bờm rất thích phân số. Do vậy anh ta viết các số đã cho dưới dạng: \(\frac{1}{x^{a_{1}}} + \frac{1}{x^{a_{2}}} + \ldots + \frac{1}{x^{a_{n}}}\). Sau đó Bờm tìm mẫu số chung và tính tổng của các phân số, kết quả tìm được có dạng là \(\frac{s}{t}\) trong đó \(t = x^{a_{1} + a_{2} + \ldots + a_{n}}\). Giờ Bờm muốn tối giản phần kết quả.

Giúp Bờm tìm ước chung lớn nhất của số \(s\) và \(t\). Kết quả tìm được có thể rất lớn, do vậy in ra số dư sau khi chia cho số 1000000007.

Dữ liệu:

- Dòng đầu ghi hai số nguyên dương \(n\) và \(x\ (1 \leq n \leq 10^{5},2 \leq x \leq 10^{9})\) – kích thước của mảng và số nguyên tố.

- Dòng thứ hai ghi \(n\) số nguyên \(a_{1},\ a_{2},\ \ldots,\ a_{n}\ (0 \leq a_{1} \leq a_{2} \leq \ldots \leq a_{n} \leq 10^{9})\)

Kết quả:

- In ra một số nguyên – phần dư của kết quả tìm được chia cho \(1000000007\ (10^{9} + 7)\)

Ví dụ 1:

Ví dụ 2:

Ví dụ 3: