Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Prime Number

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSimon 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*^{a1 + a2 + ... + an}. 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 (10^{9} + 7).

Input

The first line contains two positive integers *n* and *x* (1 ≤ *n* ≤ 10^{5}, 2 ≤ *x* ≤ 10^{9}) — 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} ≤ 10^{9}).

Output

Print a single number — the answer to the problem modulo 1000000007 (10^{9} + 7).

Examples

Input

2 2

2 2

Output

8

Input

3 3

1 2 3

Output

27

Input

2 2

29 29

Output

73741817

Input

4 5

0 0 0 0

Output

1

Note

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/17/2018 23:16:37 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|