欧拉通行证

题目描述

数据保证 gcd(a,m)=1，指数 N 是超长十进制正整数。枚举求欧拉函数 φ(m)，将指数按φ(m)缩小后计算 a^N mod m。

输入格式

一行输入 a、数字字符串N、m，满足 1≤m≤2×10^4、0≤a≤10^18、gcd(a,m)=1；N表示正整数，长度不超过10^5。

输出格式

输出 a^N 的标准余数。m=1时输出0。

样例

输入

2 2026 9

输出

7