Description

输入b，p，k的值，求$b^p$ mod k的值。其中b，p，k为整型数。 b,p均不超过整型范围，$k^2$不超过整型。

Format

Input

第1行:3个空格分开的整数b, p, k

Output

第1行：1个数表示运算结果。

Samples

2 10 9

7