给你一个素数 $$$p$$$、$$$n$$$ 整数 $$$a_1、a_2、\ldots、a_n$$$ 和整数 $$$k$$$。
求 $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) 的索引对数量,其中 $$$(a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p$$$。
输入
第一行包含整数 $$$n, p, k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$2 \le p \le 10^9$$$, $$$0 \le k \le p-1$$$)。 $$$p$$$ 保证是素数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le p-1$$$)。保证所有元素都不同。
输出
输出一个整数——问题的答案。
示例
输入 #1
3 3 0 0 1 2
输出 #1
1
输入 #2
6 7 2 1 2 3 4 5 6
输出 #2
3
注意
在第一个示例中:
$$$(0+1)(0^2 + 1^2) = 1 \equiv 1 \bmod 3$$$。
$$$(0+2)(0^2 + 2^2) = 8 \equiv 2 \bmod 3$$$。
$$$(1+2)(1^2 + 2^2) = 15 \equiv 0 \bmod 3$$$。
因此只有 $$$1$$$ 对满足条件。
在第二个示例中,有 $$$3$$$ 这样的对:$$$(1, 5)$$$、$$$(2, 3)$$$、$$$(4, 6)$$$。