题目描述

输入整数m，n，k，求m^n mod k的值。m，n，k*k为长整型范围内的自然数。

输入格式

输入一行3个整数，分别为m，n，k。

输出格式

输出一行整数，表示结果。

样例数据

input

2    10    9

output

7