该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近跟石老师进行了数学的地狱训练

今天他碰到了一个难题！

石老师给徐老师随机写了一个长度为 $n$ 的序列 $a_1 \sim a_n$ 和一个质数 $p$

让徐老师求有多少个数对 $(i, j)$ 满足：

1. $1 \leq i, j \leq n$
2. $i \neq j$
3. $a^2_i + a_i + a^2_j \equiv a_i \times a_j \pmod{p}$。

现在徐老师被这个问题难住了，请你帮他计算一下

P.S. 你可以将 $A \equiv B \pmod{p}$ 简单的理解为 $A\ mod\ p = B\ mod\ p$

输入格式

输入第一行为两个正整数 $n, p$，含义如题

输入第二行为 $n$ 个正整数，分别表示 $a_1 \sim a_n$

输出格式

输出一个整数，表示满足条件的数对个数。

数据范围

对于全部测试点满足：$1 \leq n \leq 5 \times 10^5, 1 \leq p \leq 10^9 + 30$， $1 \leq a_i < \left\lfloor \frac{p}{2} \right\rfloor$，且保证 $p$ 是质数。

样例输入1

6 17
6 3 5 2 4 1

样例输出1

4

样例解释1

数对 $(1, 4), (1, 5),(5, 2), (5, 6)$ 满足条件。