[백준] 1629 곱셈

문제링크: www.acmicpc.net/problem/1629

1629번: 곱셈

power

import java.io.*;
import java.util.*;
public class Main {
	public static long N,M,K;
	
	public static long power(long num,long cnt) {
		if(cnt==0) return 1;
		long temp = power(num,cnt/2);
		temp = temp*temp % K;
		if(cnt%2==1) {
			temp*=num % K;
		}
		return temp % K;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Long.parseLong(st.nextToken());
		M = Long.parseLong(st.nextToken());
		K = Long.parseLong(st.nextToken());
		System.out.println(power(N,M));
	}

}