题目描述

$P$ 工厂是一个生产纸箱的工厂。纸箱生产线在人工输入三个参数 $n,p,a$ 之后，即可自动化生产三边边长为：

（$a \bmod p$，$a^2 \bmod p$，$a^3 \bmod p$）
（$a^4 \bmod p$，$a^5 \bmod p$，$a^6 \bmod p$）
$\cdots$
（$a^{3n-2} \bmod p$，$a^{3n-1} \bmod p$，$a^{3n} \bmod p$）

的 $n$ 个纸箱。在运输这些纸箱时，为了节约空间，必须将它们嵌套堆叠起来。一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。这里不考虑任何旋转后在对角线方向的嵌套堆叠。

你的任务是找出这 $n$ 个纸箱中数量最多的一个子集，使得它们两两之间都可嵌套堆叠起来。

输入格式

输入文件的第一行三个整数，分别代表 $a,p,n$。

输出格式

输出文件仅包含一个整数，代表数量最多的可嵌套堆叠起来的纸箱的个数。

10 17 4

2

样例说明 1

生产出的纸箱的三边长为（$10,15,14$），（$4,6,9$），（$5,16,7$），（$2,3,13$）。其中只有（$4,6,9$）可堆叠进。

（$5,16,7$），故答案为 $2$。

数据规模与约定

$100\%$ 的数据满足：$2 \le p \le 2 \times 10^9$，$1 \le a \le p-1$，$a^k \bmod p > 0$，$a \cdot p \le 2 \times 10^9$，$1 \le n \le 5 \times 10^4$。