Your are given integer numbers \textbf{A}, \textbf{B} and \textbf{C}. Output the remainder of division \textbf{A^B} (\textbf{B}-th power of \textbf{A}) by \textbf{C}. \textbf{Input} The only line of the input file contains three integers: \textbf{A}, \textbf{B}, \textbf{C} (\textbf{1} <= \textbf{A}, \textbf{B}, \textbf{C} <= \textbf{10^18}). Numbers are separated by spaces. \textbf{Output} Output file must contain only one non-negative integer less than \textbf{C} - the answer to the problem.