大指数落在哪间房

题目描述

给定 a、n、m，求 a^n mod m。可利用从 r_0=1 mod m 开始的余数序列前导段与循环节定位第n项。

输入格式

一行输入 a、n、m，满足 0≤a≤10^9、0≤n≤10^18、1≤m≤2×10^5。

输出格式

输出 a^n 的标准余数。本题约定任何a（包括0）的0次方为1。

样例

输入

2 2026 5

输出

4