거듭 제곱 구하기 L

문제

n과 m이 주어질 때, n의 m승을 구하는 프로그램을 작성하시오. 단, n의 m승의 값이 커질 수 있기 때문에, 정답을 10,007 으로 나눈 나머지를 출력한다.

 

입력

첫 번째 줄에 숫자 n과 m이 주어진다. ( 1 ≤ n ≤ 100, 1 ≤ m ≤ 1,000,000,000,000,000,000 )  

출력

첫째 줄에 n의 m승을 10,007 으로 나눈 나머지를 출력한다.

 

예제 입력

3 4

예제 출력

81

 

#코드

import sys
 
'''
(1) 함수의 정의 : 함수의 의미를 "말로" 정의한다.
(2) 점화식 : 나보다 작은 함수는 값을 잘 구한다고 가정하고,
             이들을 이용해서 나를 구하기 위한 식을 접는다.
(3) 기저조건   
 
'''
def getResult(n, m):
  # n^m을 10007로 나눈 나머지를 반환하는 함수
  # m == 0 기저 조건
  if m == 0:
    return 1
  else:
    if m%2 == 0:
      # n^m = (n^(m//2))^2
      temp = getResult(n, m//2)
      return (temp*temp)%10007
    else:
      # n^m = (n^(m-1))*n
      temp = getResult(n, m-1)
      return (temp*n)%10007
 
if __name__ == "__main__":
  n, m = map(int, sys.stdin.readline().split())
  print(getResult(n,m))