veeeliki
You are given a biiiiiig number N and even biiiiiigger number K. Your task is to find the value of expression \mathbf{N^{K}} (mod M) (in other words, you have to find the remainder of division \mathbf{N^{K}} with M).
InputIn input, you are given three natural numbers N, K and M (2 \leq M < 2^{31}), where numbers N and K can consist of up to 1 000 000 digits each. Each number is in a separate row.
OutputOn first and only line of the output, write the value of the expression \mathbf{N^{K}} (mod M).
Input
Output
11
2
7Output
2 Input
Output
2
12
15Output
1 Input
Output
123456789023454578455454
982121217654321111110
514567 Output
231054 Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.