题目描述

给定三个正整数 $b,p,k$，求 $b^p$ 除以 $k$ 的余数。

输入格式

一行三个整数 $b,p,k$。

输出格式

输出余数。

样例

2 10 9

7

数据范围

$1\le b,p\le2147483647$，$1\le k\le46340$，即 $k^2\le2147483647$。