#PW2. 幂取模

幂取模

题目描述

输入三个正整数 a,b,ma, b, m,输出 ab mod ma^b \bmod m。

输入格式

一行三个正整数 a,b,ma, b, m,用空格隔开。

输出格式

一行,一个整数。

样例

2 10 1000
24

数据范围

1≤a,m≤1091 \le a, m \le 10^9,1≤b≤1091 \le b \le 10^9。

提示

用快速幂,每次乘完都对 mm 取模。