题目背景

伴随着“砰”的一声闷响，小骑士的落下溅起了许多碎石，直起身子，披风在风中飘舞，他开始仔细打量这个

新颖的世界，但是一个问题出现了，他没有钱！可他找了许久也不知道这里的钱长成何样，就在要放弃时，小

骑士被石子绊倒，跌进了一片黑影中。待到他爬起身，眼前赫然是……成堆的吉欧！（钱）

题目描述

小骑士欣喜若狂，真的希望直接将所有的吉欧一股脑装入口袋，但奈何，他并不知道这里共有多少吉欧。

小骑士看到了旁边一份遗属，才知道原来这是一位死去的虫子留下的。

并且从遗嘱中可知，这里一共有：$p^k$ 个吉欧，由于吉欧数量庞大，需要对 $mod$ 取模

输入格式

第一行包括三个整数 $p, k, mod.$

接下来一行输出 $p^k$ 模 $mod$ 后的结果。

（提示：快速幂）

输出格式

输出一行一个整数表示答案。

2 10 9

7

6 77045 14759

2452

数据规模与约定

对于所有的数据，均满足 $0<=p,k<=2^{31},2<=mod<=2^{31}$ .