Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P194PROF - Problem F - Số nguyên tố

Cho số nguyên tố x và một dãy các số nguyên không âm a1, a2, ..., an.

Đặt:

$$\frac{s}{t}=\frac{1}{x^{a_1}} + \frac{1}{x^{a_2}} + ... + \frac{1}{x^{a_n}}$$

Trong đó

$$t=x^{a_1+a_2+...+a_n}$$

Bạn hãy tính ước chung lớn nhất của s và t (lấy dư cho 109 + 7).

Input

Dòng đầu tiên chứa hai số nguyên n và x  (1 ≤ n ≤ 100000, 2 ≤ x ≤ 109) - số lượng phần tử của dãy số và số nguyên tố.

Dòng tiếp theo gồm n số nguyên a1, a2, ..., an (0 ≤ ai ≤ 109)

Output

In ra  ước chung lớn nhất của s và t (lấy dư cho 109 + 7).

Example

Input:
3 3
1 2 3

Output:
27

Được gửi lên bởi:adm
Ngày:2019-03-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.