세 정수 a, b, m 이 공백으로 구분되어 주어집니다. (1 <= a <= 10^9, 0 <= b <= 10^18, 1 <= m <= 10^9)
a
b
m
1 <= a <= 10^9
0 <= b <= 10^18
1 <= m <= 10^9
a 를 b번 곱한 값을 m 으로 나눈 나머지를 출력하세요.
b 가 매우 크므로 b번 반복하면 시간 안에 끝나지 않습니다. 지수를 절반으로 나누는 방법을 생각해보세요.
입력
2 10 1000
출력
24
3 0 7
1