小月的计数
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给定整数 A,B 与整数模数 m，计算整数对 (x,y) 的数量，使得 0 \leq x, y \lt m 且满足：

x^A\equiv y^B\pmod m

【名词解释】
\hspace{15pt}a \equiv b \pmod m：同余关系，表示 a 除以 m 的余数与 b 除以 m 的余数相同。

输入描述:

\hspace{15pt}在一行上输入三个整数 A,B,m \left(1\leq A,B\leq 10^{18};\, 1\leq m\leq 10^6\right)。

输出描述:

\hspace{15pt}输出一个整数，表示满足的有序数对的个数（精确计算）。
示例1

输入

复制 
1 2 3

输出

复制 
3

说明

\hspace{15pt}在这个样例中：
\hspace{23pt}\bullet\,整数对 (0,0)：0^1 \bmod 3 = 0、0^2 \bmod 3 = 0，同余关系成立；
\hspace{23pt}\bullet\,整数对 (0,1)：0^1 \bmod 3 = 0、1^2 \bmod 3 = 1，同余关系不成立；
\hspace{23pt}\bullet\,整数对 (0,2)：0^1 \bmod 3 = 0、2^2 \bmod 3 = 1，同余关系不成立；
\hspace{23pt}\bullet\,整数对 (1,0)：1^1 \bmod 3 = 1、0^2 \bmod 3 = 0，同余关系不成立；
\hspace{23pt}\bullet\,整数对 (1,1)：1^1 \bmod 3 = 1、1^2 \bmod 3 = 1，同余关系成立；
\hspace{23pt}\bullet\,整数对 (1,2)：1^1 \bmod 3 = 1、2^2 \bmod 3 = 1，同余关系成立；
\hspace{23pt}\bullet\,整数对 (2,0)：2^1 \bmod 3 = 2、0^2 \bmod 3 = 0，同余关系不成立；
\hspace{23pt}\bullet\,整数对 (2,1)：2^1 \bmod 3 = 2、1^2 \bmod 3 = 1，同余关系不成立；
\hspace{23pt}\bullet\,整数对 (2,2)：2^1 \bmod 3 = 2、2^2 \bmod 3 = 1，同余关系不成立。
\hspace{15pt}综上，满足条件的整数对有 (0,0)、(1,1)、(1,2) 三组。
示例2

输入

复制 
1145141919810 1919810 114514

输出

复制 
2223186