시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 34 8 6 28.571%

문제

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

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자리를 맞춘 뒤 출력한다.

예제 입력

2
4
7
10
10
6
3
10
7
0

예제 출력

0065536
000000
4195387

힌트