Exponentiation is a mathematical operation that involves raising a base number to a certain exponent to obtain a result. In the expression , where is the base and is the exponent, it means multiplying by itself times. The result of this operation is called the exponentiation of to the -th power. For examples, and . In these examples, 2 is the base, 3 is the exponent in the first case, and 5 is the base, and 2 is the exponent in the second case. Exponentiation is a fundamental operation in mathematics and is commonly used in various contexts, such as solving equations, and cryptography.
In many cryptographic algorithms, particularly those based on number theory like RSA (Rivest-Shamir-Adleman) and Diffie-Hellman, modular exponentiation is a fundamental operation. Modular exponentiation involves raising a base to an exponent modulo a modulus. This operation is computationally intensive but relatively easy to perform, even for very large numbers.
Let where is a positive integer. Please write a program to compute for given positive integers and .
输入格式
The input has only one line, and it contains three space-separated positive integers , and .
输出格式
Output . If there are multiple solutions, you may output any of them in the range from to .
样例
样例输入 1
1 2 3
样例输出 1
2
样例输入 2
5 4 321
样例输出 2
206
样例输入 3
3 3 333
样例输出 3
18
样例输入 4
8 8 888
样例输出 4
626
数据范围与提示
Note
can be a complex number. For example, is either or if . However, is always an integer in this problem.
, and are positive integers less than . You may assume is an integer.
