Equal remainders

The definition of remainders and divisibility is extended from positive integers to all integers as follows.

• For an integer $a$ and a positive integer $q$, the remainder $r$ of $a$ divided by $q$ is the value with $0\le r<q$ for which $a=qx+r$ holds for some integer $x$. This is written $a\equiv r\pmod q$.
• An integer $a$ is divisible by a positive integer $q$ when the remainder of $a$ divided by $q$ is $0$.

Given a set of integers $A$ and a positive integer $M$, define $A^M$ as follows.

• $S(A) := \{ q \in \mathbb{Z}^{+} \mid \exists r \ne 0 : \forall x \in A,\ x \equiv r \pmod q \land \gcd(q, x) = 1 \}$
• $A^M := \{ \operatorname{sgn}(x) \cdot |x|^M \mid x \in A \}$

Here $\operatorname{sgn}(x) := x/|x|$ for $x\ne 0$ and $\operatorname{sgn}(0) = 0$.

In plain terms, $S(A)$ is the set of positive integers $q$ such that every element of $A$ leaves the same nonzero remainder when divided by $q$, and every element of $A$ is coprime to $q$. $A^M$ is the set of numbers that have the same sign as each element of $A$ and whose absolute value is that element's absolute value raised to the power $M$.

Given a set $A$ of $N$ distinct integers and a nonnegative integer $K$, find the smallest positive integer $M$ such that

• $\forall s\in S(A),\ s^K\in S(A^M)$

The first line contains positive integers $N$ ($2\le N\le 10^5$) and $K$ ($1\le K\le 10^{17}$), separated by a space.

The second line contains $N$ distinct integers $A_i$ ($-10^{18}\le A_i\le 10^{18}$) in ascending order, separated by spaces.

Print the smallest positive integer $M$ that satisfies the condition, modulo $10^9+7$, since the answer can be very large.

If no such $M$ exists, print -1 instead.