Calculations with Modulo
Problem
Find the answer of \((\frac {A^B}{C})\%M\).
Input:
The only line of input consists of four integers A,B,C and M. The input always has C and M such that \(gcd(C,M)=1\).
Output:
Print the answer as asked in the problem statement.
Constraints:
\(1 \le A,B,C,M \le 10^9\)
\(gcd(C,M)=1\).
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
\(2^3\)=8
so, 8/4 = 2
Finally, 2%5 = 2
