费马加速卡

题目描述

模数 p 为质数且 p∤a，指数 N 是超长十进制正整数。利用费马小定理按 p-1 缩小指数，求 a^N mod p。

输入格式

一行输入 a、数字字符串N、p。满足 2≤p≤2×10^5且p为质数，0≤a≤10^18、p∤a；N只含数字、表示正整数、长度不超过10^5。

输出格式

输出 a^N 的标准余数。

样例

输入

3 2026 7

输出

4