마지막 자리

어떤 수를 거듭제곱하면 매우 큰 수를 얻을 수 있다.

정수 $b$, $n$, $i$가 주어진다. 함수 $f$는 다음과 같이 정의된다.

$f(x) = b^{f(x-1)} \quad (x > 0), \qquad f(0) = 1$

즉 $f(i)$는 밑이 $b$이고 높이가 $i$인 거듭제곱 탑이다. 이때 $f(i)$의 마지막 $n$자리를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에는 $b$ ($1 \le b \le 100$), 둘째 줄에는 $i$ ($1 \le i \le 100$), 셋째 줄에는 $n$ ($1 \le n \le 7$)이 주어진다. 마지막 테스트 케이스 다음 줄에는 $0$이 하나 주어지며, 이는 입력의 끝을 의미한다.

각 테스트 케이스에 대해 $f(i)$의 마지막 $n$자리를 한 줄에 출력한다. 만약 $f(i)$가 $n$자리보다 작으면, 앞에 $0$을 채워 정확히 $n$자리로 맞추어 출력한다.