Efficient Power Modulo n

Max Reward: 100

Create a function that computes (x^y)%n for large y. Try not to use language builtin exponent functions, because we'll be dealing with some pretty large numbers, and the output of builtin exponent functions can get so large that they won't fit even 64-bit floats.

Be efficient, be capable of handling large inputs

Input Format

Each input will be a single line, containing the base, the exponent, and the modulus respectivly, comma-and-space separated. Example:
4, 12, 3

Output Format

The output should be a single number, which should match the calculation: (base ^ exponent) % modulus. Like this:
1

Sample Input

5, 100000000, 19

Sample Output

5

Memory Limit

512M