A satellite handshake computes a raised to a rolling counter, reduced modulo m. The counter b can be astronomically large, so it is supplied as a decimal string of up to 1000 digits. Compute (a ** b) mod m. Use the convention that a ** 0 = 1 for every a (including a = 0).
Input format
Line 1: two integers a and m.
Line 2: the exponent b as a non-negative decimal integer (it may have up to 1000 digits and may contain leading zeros).
Output format
A single integer: (a ** b) mod m.
Constraints
- 0 <= a <= 1000000000
- 1 <= m <= 1000000000
- 0 <= b, with at most 1000 decimal digits