题目描述

Aki 在研究一个模数为 $M$ 的线性递推序列。他先选定两个起始值 $x,y$（均在 $0\sim M-1$ 之间），然后按下面规则生成一个无限序列 $(s_1,s_2,s_3,\dots)$：

• $s_1=x$
• $s_2=y$
• $s_n = A\cdot s_{n-1} + B\cdot s_{n-2}\quad (n\ge 3)$

Aki 关心的是：这个序列中是否会出现 $M$ 的倍数（也就是某一项能被 $M$ 整除）。

请你统计：在所有满足 $0\le x,y\le M-1$ 的整数对 $(x,y)$ 中，有多少对能使得序列 $(s_1,s_2,\dots)$ 从始至终都不包含 $M$ 的倍数。

输入格式

一行三个整数 $M,A,B$。

数据规模：

• $2\le M\le 1000$
• $0\le A,B\le M-1$
• 输入均为整数。

输出格式

输出一个整数，表示满足条件的整数对 $(x,y)$ 的数量。

4 1 2

7

Hint

样例解释： 满足条件的 $(x,y)$ 一共有 7 对： $(1,1),(1,3),(2,1),(2,2),(2,3),(3,1),(3,3)$。

例如取 $(x,y)=(2,1)$，序列为 $(2,1,5,7,17,31,\dots)$，其中没有 4 的倍数；
而取 $(x,y)=(3,2)$ 时，$s_3=8$ 是 4 的倍数，因此不满足条件。