Execution time limit is 1 second Runtime memory usage limit is 128 megabytes Three positive integers x,n and m are given. Find the value of xn mod m.
Input
Three positive integers x,n,m (1≤x,m≤109,2≤n≤107).
Output
Find and print the value of xn mod m.
Examples