마지막 자리

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

b, n, i가 주어진다. f(x)는 f(x) = bf(x-1) (x>0), f(0) = 1로 정의되어 있다. 이때, f(i)의 마지막 n자리를 구하는 프로그램을 작성하시오.

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

각 테스트 케이스에 대해서, f(i)의 마지막 n자리를 출력한다. 만약 결과가 n자리보다 작을 때는, 앞에 0을 채워 n자리를 맞춘 뒤 출력한다.