Competitions
DSA Week 1
Modular Exponentiation
Three positive integers x, n and m are given. Find the value of x^n~mod~m.
Input data
Three positive integers x, n, m~(1 \le x, m \le 10^9, 2 \le n \le 10^7).
Output data
Find and print the value of x^n~mod~m.
Examples
Input example #1
2 3 100
Output example #1
8