세 정수 base, exponent, mod를 받아 base의 exponent제곱을 mod로 나눈 나머지를 반환하는 함수 RecursivePower를 작성하시오. 지수를 절반으로 나누는 재귀 호출을 사용해야 하며, 같은 단계에서 같은 재귀 호출을 두 번 실행하지 않도록 그 결과를 변수에 저장해야 한다.

함수 원형은 주어지지 않는다. 설명과 아래의 호출 코드를 보고 함수의 매개변수와 반환값을 직접 설계한다.

함수를 사용하는 코드

작성한 함수는 아래 코드와 함께 실행된다.

base, exponent, mod = map(int, input().split())

result = RecursivePower(base, exponent, mod)
print(result)
print(type(result))

위 코드가 정상적으로 동작하도록 함수를 직접 정의한다. 제출할 때는 작성한 함수의 정의 전체만 제출한다.

입력

첫째 줄에 base, exponent, mod가 주어진다.

• \(-1,000,000,000 \le base \le 1,000,000,000\)
• \(0 \le exponent \le 1,000,000,000,000,000,000\)
• \(1 \le mod \le 1,000,000,000\)

출력

base의 exponent제곱을 mod로 나눈 나머지를 출력한다. exponent가 0이면 1 % mod를 반환한다. 함수는 int를 반환해야 한다.

마지막 줄에는 함수가 반환한 값의 자료형을 출력한다.

금지 키워드

다음 문자열은 소스 코드에 포함될 수 없다.

• pow
• **

예제 입력 1

2 10 1000

예제 출력 1

24
<class 'int'>

예제 입력 2

3 0 7

예제 출력 2

1
<class 'int'>