Description

【题意】
给你一个$2n+2$的整数数列
$A_0=0,A_1=C$
$A_{i+2}=(A_{i+1}+A_i)\ mod\ M$
现在有$n$个平面向量
$V_1=(A_2,A_3),V_2=(A_4,A_5)...V_n=(A_{2n},A_{2n+2})$
要求你求两两向量的数量积mod M出现了多少个
即求集合$S$的大小，其中$S=\{(V_i\cdot V_j)\ mod\ M|1\leq i,j\leq n,i\neq j\}$
对于两个向量$(x1,y1),(x2,y2)$，它们的数量积为$x1x2+y1y2$
【输入格式】
三个整数$C,m,n$
【输出格式】
输出一个整数代表答案
【样例输入】
4 5 3
【样例输出】
2
【提示】
数列为${0,4,4,3,2,0,2,2},v1=(4,3),v2=(2,0),v3=(2,2)$。
$v1\cdot v2\ mod\ M=3,v2\cdot v3\ mod\ M=4,v1\cdot v3\ mod\ M=4$。
对于100%的数据，$1≤C≤10^9,1≤M≤10^9,1≤n≤3*10^5$