#222EasyMath & Number Theory· Fast Modular Exponentiation

Modular Power Checksum

A warehouse scanner protects each parcel label with a checksum: the label stores the value of `base^exponent` taken modulo a public number `modulus`. The exponent is huge, so the scanner cannot multiply `base` by itself that many times. Given `base`, `exponent` and `modulus`, return `(base^exponent) mod modulus`. By convention `base^0 = 1`, so the result for a zero exponent is `1 mod modulus` (which is `0` when the modulus is `1`).

Input format

`base`, `exponent` and `modulus` as integers.

Output format

An integer in `[0, modulus - 1]`.

Examples

Input: base = 2, exponent = 10, modulus = 1000

Output: 24

2^10 = 1024 and 1024 mod 1000 = 24.

Input: base = 3, exponent = 200, modulus = 13

Output: 9

3^3 = 27 = 1 (mod 13), so 3^200 = 3^(3*66 + 2) = 3^2 = 9 (mod 13).

Input: base = 10, exponent = 5, modulus = 1

Output: 0

Every integer is 0 modulo 1.

Constraints

0 <= base <= 10^9
0 <= exponent <= 10^9
1 <= modulus <= 10^9
Intermediate products can exceed 32 bits: widen them before taking the remainder.

#math
#modular-arithmetic
#exponentiation
#number-theory