Exponents

Time limit: 1 s.
Memory limit: 256 MB

Given 3 integers \(A\), \(B\) and \(M\). Compute: \(A ^ B \mod M\)

Input

The input consists of \(3\) integers \(A\), \(B\) and \(M\). \((0 \le A, B \le 10^6), (1 \le M \le 10^9)\)

Output

Output the value of \(A ^ B \mod M\)

Scoring

Group Constraints Points
\(1\) \(A \equiv 0 \pmod{M}\) \(13\)
\(2\) \(A \equiv 1 \pmod{M}\) \(11\)
\(3\) \(A \equiv M-1 \pmod{M}\) \(35\)
\(4\) — \(41\)

Examples

Input

2 3 10

Output

8

Input

10 3 5

Output

0

Input

7 100 6

Output

1
Solution

Use binary exponentiation. While \(B>0\), square the base at every step. If the current bit of \(B\) is \(1\), multiply it into the answer. All values are reduced modulo \(M\) immediately.

This takes \(O(\log B)\) time and \(O(1)\) memory.

#include <iostream>
using namespace std;

int main() {
    long long a, b, m;
    cin >> a >> b >> m;

    a %= m;
    long long answer = 1 % m;

    while (b > 0) {
        if (b % 2 == 1) {
            answer = answer * a % m;
        }
        a = a * a % m;
        b /= 2;
    }

    cout << answer << '\n';
}