【问题描述】

定义“取模’’运算：对于正整数a和p,a％p表示a除以p的余数，又称“模”运算。

现在，输入三个正整数b、p、k，请编程计算b^p％k的值。

【输入格式】

一行三个正整数，分别表示b,p,k的值。其中，b,p,k*k<=2147483647。

【输出格式】

一行一个整数，表示b^p%k的值。

【输入样例】

2 10 9

【输出样例】

7