[백준] 1629번 곱셈 문제! (silver 1

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        long a=Long.parseLong(st.nextToken());
        long b=Long.parseLong(st.nextToken());
        long c=Long.parseLong(st.nextToken());
        System.out.println(mul(a,b,c));
    }
    public static long mul(long a,long b,long c){
        a%=c;
        if(b==1){
            return a;
        }
        else if(b%2==0){
            return mul(a*a , b/2, c);
        }
        else{
            return a*mul(a*a, (b-1)/2,c)%c;
        }
    }
}