Migrated from Lutece 3019 简单数论

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

这是一道 简单数论 ，因为只要想到关键之处，那就真的很简单。

$p$ 是一个质数，$a$ 和 $b$ 是两个正整数，在 $mod \space p$ 意义下，设 $a$ 的逆元为 $x$ ， $b$ 的逆元为 $y$ 。

注意：Constraints中阐述了 $a$ 和 $b$ 的范围，在这个范围中，显然满足 $(a,p)=(b,p)=1$ ，因此 $a$ 和 $b$ 在 $mod \space p$ 意义下的逆元一定存在。

现在maco要构造一个长度为 $p$ 的序列 $A=(A_1,A_2,...,A_p)$ ，对于 $i∈[1,p-1]$ ，计算正整数 $c_i$ ，满足 $c_i≡A_{i+1}*A_i^{-1}(mod \space p)$ 且 $0≤c_i≤p-1$ ，显然当序列 $A=(A_1,A_2,...,A_p)$ 确定时，这样的 $c_i$ 也是存在且唯一确定的。

maco希望这个长度为 $p$ 的序列 $A=(A_1,A_2,...,A_p)$ 能够满足下面的要求：

（1）$A_1=A_p=1$

（2） $(A_1,A_2,...,A_{p-1})$ 是 $(1,2,...,p-1)$ 的一个排列

（3）对于任意的 $i∈[1,p-1]$ ，$c_i$ 都等于 $a$，$b$，$x$，$y$ 中的一个

请你判断 maco 能否构造出满足上述要求的序列

Input

输入三个整数 a,b,p

Output

输出答案 如果存在这样的序列，输出"YES"，否则输出"NO"

Samples

4 5 13

YES

9 3 13

NO

Constraints

$2≤p≤10^5$ $1≤a,b,x,y≤p-1$ $1≤A_i≤p-1$

Note

解释一下样例： 对于第一组样例，可以构造出 $A=(1,5,11,3,12,9,7,4,6,8,2,10,1)$ 对于第二组样例，无法构造出满足要求的序列

如果不会做，大家可以尝试回忆一下maco上课讲了什么。 （maco已经很认真地在讲课了，求求大家认真听吧）

Resources

2023 UESTC ICPC Training for Math