Problem Background

The problem setter also wants to write interesting problem statements, but unfortunately lacks the ability to do so.

Problem Description

You are given three positive integers, \(a, m, b\). You need to compute: \(a^b \bmod m\)

Input Format

A single line containing three integers, \(a, m, b\).

Output Format

A single integer representing the answer.

Sample Input and Output

Sample Input #1

2 7 4

Sample Output #1

2

Sample Input #2

998244353 12345 98765472103312450233333333333

Sample Output #2

5333

Notes

Note the input format, where \(a, m, b\) represent the base, modulus, and exponent respectively.

Sample 1 Explanation

\(2^4 \bmod 7 = 2\)

Data Range

For 100% of the data, \(1 \le a \le 10^9\), \(1 \le b \le 10^{20000000}\), \(1 \le m \le 10^8\).

见题面 Input 部分

见题面 Output 部分