#2253. [2010 Beijing wc]纸箱堆叠

内存限制:256 MiB 时间限制:30 Sec

题目描述

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

(a mod P,a^2 mod p,a^3 mod P)
(a^4 mod p,a^5 mod p,a^6 mod P)
....
(a^(3n-2) mod p,a^(3n-1) mod p,a^(3n) mod p)

的n个纸箱。在运输这些纸箱时,为了节约空间,必须将它们嵌套堆叠起来。
一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边
长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。这里不考虑
任何旋转后在对角线方向的嵌套堆叠。
你的任务是找出这n个纸箱中数量最多的一个子集,使得它们两两之间都可
嵌套堆叠起来。

输入格式

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

输出格式

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

样例

样例输入


			
10 17 4

样例输出


			

2
【样例说明】
生产出的纸箱的三边长为(10, 15, 14), (4, 6, 9) , (5, 16, 7), (2, 3, 13)。其中只有
(4, 6, 9)可堆叠进(5, 16, 7),故答案为 2。
2<=P<=2000000000,1<=a<=p-1,a^k mod p<>0,ap<=2000000000,1<=N<=50000

数据范围与提示