Problem Description

Houraisan Kaguya is fighting against Fujiwara no Mokou over the moon. Suddenly, Mokou launches a spell “Imperishable Shooting”(just a programming problem, believe it or not) to attack Kaguya, which is as follows.
Given a prime number p and n positive integers a1, a2, · · · , an which are strictly less than p.
For two integers a, b (0 ≤ a, b < p), we say a is representable by b if and only if there exists a positive integer x that bx ≡ a(mod p). Furthermore, we define f(a, b) as the minimum positive integer u that au modulo p is representable by b. If no such u exists, f(a, b) is specially defined as 0.
The problem is to determine the value of following formula.
$$(\sum_{i=1}^{n}\sum_{j=1}^{n}f(a_i,a_j)\times f(a_j,a_i)) \mod p$$
Please help Kaguya solve it so that Kaguya can give Mokou the sixth puzzle in the next round.

Input

The first line contains two positive integers n, p (1 ≤ n ≤ 100 000, 2 ≤ p ≤ 1018), denoting the number of given integers and the given prime number.
The next line contains n positive integers ai (1 ≤ ai < p), denoting the given integers.

Output

Output a single line containing a non-negative integer, denoting the answer.

4 5
1 2 3 4

4