Volumes > C. T. 2011 > problem:

A to the power of B

If you notice incorrect translations in Contester, please let author know.

Time limit 1000/1000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.

Problem description

Given three numbers a, b and n. Calculate a^b mod n (a^b % n) .

Input

In a single line of input given three numbers a, b and n (0 < a, n < 1001; 0 < b < 2³¹).

Output

Write the value of a^b mod n (a^b % n).

Example

stdin	stdout
2 5 1000	32

Для отправки решений необходимо выполнить вход.