재귀 3: 거듭제곱

문제

정수 (a)와 (b)가 주어진다. (a^b)를 (1{,}000{,}000{,}007)로 나눈 나머지를 재귀 함수로 구하라.

점화식은 (f(a, b) = a \times f(a, b-1)), (f(a, 0) = 1)이다. 곱할 때마다 나머지를 취하면 값이 커지지 않는다.

예시

입력