나머지가 같아지도록

나머지와 나누어떨어짐의 정의를 양의 정수뿐만 아니라 정수 전체로 확장하면 다음과 같다.

• 정수 $a$를 양의 정수 $q$로 나눈 나머지 $r$은, $a=qx+r$을 만족하는 정수 $x$가 존재하고 $0\le r<q$인 값으로 정의한다. 이를 $a\equiv r\pmod q$로 나타낸다.
• 정수 $a$가 양의 정수 $q$로 나누어떨어진다는 것은 $a$를 $q$로 나눈 나머지가 $0$이라는 뜻이다.

정수 집합 $A$가 주어진다. 양의 정수 $M$에 대하여 $A^M$을 다음과 같이 정의한다.

• $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 \}$

단, $\operatorname{sgn}(x) := x/|x|$ ($x\ne 0$)이고 $\operatorname{sgn}(0) = 0$인 부호함수이다.

쉽게 말해, $S(A)$는 $A$의 모든 원소를 $q$로 나눈 나머지가 같은 0이 아닌 값이 되고, $A$의 모든 원소가 $q$와 서로소인 양의 정수 $q$들의 집합이다. $A^M$은 $A$의 각 원소와 부호가 같고 절댓값이 $M$제곱인 원소들로 이루어진 집합이다.

서로 다른 $N$개의 원소로 이루어진 정수 집합 $A$와 음이 아닌 정수 $K$가 주어진다. 다음 조건을 만족하는 최소의 양의 정수 $M$을 구하라.

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

첫 번째 줄에 양의 정수 $N$ ($2\le N\le 10^5$)과 $K$ ($1\le K\le 10^{17}$)가 공백으로 구분되어 주어진다.

두 번째 줄에 서로 다른 정수 $A_i$ ($-10^{18}\le A_i\le 10^{18}$) $N$개가 오름차순으로 공백으로 구분되어 주어진다.

조건을 만족하는 최소의 양의 정수 $M$을 $10^9+7$로 나눈 나머지를 출력한다. 답이 매우 커질 수 있기 때문이다.

조건을 만족하는 $M$이 존재하지 않으면 $M$ 대신 -1을 출력한다.