14. 거듭 제곱 구하기 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

예제 출력

8

 

#include <stdio.h>

long long int n,m;

long long int power(long long int p){
  if(p==0) return 1;
  if(p==1) return n;
  if(p%2==0){
  	long long int temp = power(p/2);
    return (temp * temp) % 10007;
  }else{
  	long long int temp = power(p-1);
    return (temp * n) %10007;
  }
}

int main(){
    scanf("%lld %lld",&n,&m);
    
    long long int result = power(m);
    
    printf("%lld",result);
    
    return 0;
}