C. The Orb of Orbits
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
During a night shift at the museum, Sherlock Holmes, bored and short on money, noticed a remarkably elegant artifact left behind by an ancient civilization. The object had a planet-like spherical shape, divided into $$$n$$$ horizontal levels. Each level $$$i$$$ was divided into $$$a_i$$$ identical sections of equal surface area, and each section could be colored independently using one of $$$K$$$ colors known to the ancients. While examining the artifact, Sherlock discovered that each horizontal level could be rotated independently around the vertical axis. At one moment, the artifact nearly slipped from his hands, and when he caught it again, he was unable to determine which side was originally facing upward, as the object appeared unchanged. Knowing that only a few such artifacts exist worldwide, Sherlock wondered how many fundamentally different artifacts are possible, where two artifacts are considered different if no sequence of allowed rotations can make them look identical.

https://wx9ydm.csb.app/

Input

The first line contains two integers $$$n$$$ and $$$K$$$ ($$$1 \le n \le 200,000$$$, $$$1 \le K \le 10^9$$$) — the number of levels and the number of colors.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 200,000$$$) — the size of each level.

Output

For each test case, output a single integer — the number of fundamentally different artifacts modulo $$$10^9 + 7$$$.

Examples
Input
5 3
4 2 1 2 4
Output
31320
Input
5 3
4 2 1 4 2
Output
62208