题目描述

给定一个质数 $p$、$n$ 个整数 $a_1, a_2, \ldots, a_n$ 和一个整数 $k$。

求满足 $(a_i \oplus a_j)(a_i^2 \oplus a_j^2) \equiv k \pmod p$ 的下标对 $(i, j)$ ($1 \le i < j \le n$) 的数量。

其中 $\oplus$ 表示按位异或运算。

输入

第一行包含三个整数 $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$)。保证所有元素互不相同。

输出

输出一个整数 — 问题的答案。

样例说明

在第一个样例中：

$(0\oplus1)(0^2 \oplus 1^2) = 1 \equiv 1 \pmod 3$.

$(0\oplus2)(0^2 \oplus 2^2) = 8 \equiv 2 \pmod 3$.

$(1\oplus2)(1^2 \oplus 2^2) = 15 \equiv 0 \pmod 3$.

因此只有 $1$ 对满足条件。

在第二个样例中，有 $3$ 对满足条件： $(1, 5)$, $(1, 6)$, $(3, 6)$。

3 3 2
0 1 2

1

6 11 2
1 3 5 6 7 8

3