素域椭圆曲线数点

题目描述

这是一道模板题。

给定质数 $p\ge 5$，$a,b\in\mathbb{F}_p$ 满足 $4a^3+27b^2\ne 0$。

求椭圆曲线 $y^2z=x^3+axz^2+bz^3$ 的点的个数。满足方程的一组不全为 $0$ 的 $(x,y,z)\in\mathbb{F}_p^3$ 称为椭圆曲线上的点，若 $\lambda\in\mathbb{F}_p$，$\lambda\ne 0$，那么 $(x,y,z)$ 和 $(\lambda x,\lambda y,\lambda z)$ 被考虑为同一个点。

输入格式

一行，三个整数 $p,a,b$，用空格分隔。

输出格式

一行，一个正整数表示答案。

样例 1

输入

7 1 3

输出

6

说明

$6$ 个点分别为 $(0,1,0),(4,1,1),(4,6,1),(5,0,1),(6,1,1),(6,6,1)$。

样例 2

输入

318743863128339547 105037157051741234 168782265549960835

输出

318743863620705102

数据范围与提示

保证 $5\le p<2^{60}$，$0\le a,b<p$。