Description

输入三个正整数a,b,m，求a^b %m的值

Input Format

三个正整数a,b,m

Output Format

一个正整数，表示a^b %m的值

Sample

样例输入

2 100 1007

样例输出

169

Hint

a,b,m<=10^9