Coding Problems and Solution ( HackerEarth: Number Theory - 1)

This problem was posted by HackerEarth.

Problem Statement:

Find the answer of $\left(\frac{A^B}{C}\right)\%M$.

Input :

TThe 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$.

Sample Input 0

2 3 4 5

Sample Output 0

2

Solution