시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 36 9 7 30.435%

문제

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

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

예제 입력 1

2
4
7
10
10
6
3
10
7
0

예제 출력 1

0065536
000000
4195387
W3sicHJvYmxlbV9pZCI6IjQ4NjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNzkwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM1YjRcdWI1YTRcdWMyMThcdWI5N2MgXHVhYzcwXHViNGVkXHVjODFjXHVhY2YxXHVkNTU4XHViYTc0IFx1YjllNFx1YzZiMCBcdWQwNzAgXHVjMjJiXHVjNzkwXHViOTdjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRiLCBuLCBpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gZih4KVx1YjI5NCBmKHgpID0gYjxzdXA+Zih4LTEpPFwvc3VwPiAoeCZndDswKSwgZigwKSA9IDFcdWI4NWMgXHVjODE1XHVjNzU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgZihpKVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5Yzkgblx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzEzOCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHVjOWY4XHVjOTA0XHVjNWQwXHViMjk0IGIoMSAmbGU7IGIgJmxlOyAxMDApLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGkoMSAmbGU7IGkgJmxlOyAxMDApLCBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG4oMSAmbGU7IG4gJmxlOyA3KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgZihpKVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5Yzkgblx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjYjBcdWFjZmNcdWFjMDAgblx1Yzc5MFx1YjlhY1x1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDQgXHViNTRjXHViMjk0LCBcdWM1NWVcdWM1ZDAgMFx1Yzc0NCBcdWNjNDRcdWM2Y2Mgblx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWI5ZGVcdWNkOTggXHViNGE0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0ODYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFzdCBEaWdpdHMiLCJkZXNjcmlwdGlvbiI6IjxwPkV4cG9uZW50aWF0aW9uIG9mIG9uZSBpbnRlZ2VyIGJ5IGFub3RoZXIgb2Z0ZW4gcHJvZHVjZXMgdmVyeSBsYXJnZSByZXN1bHRzLiBJbiB0aGlzIHByb2JsZW0sIHdlIHdpbGwgY29tcHV0ZSBhIGZ1bmN0aW9uIGJhc2VkIG9uIHJlcGVhdGVkIGV4cG9uZW50aWF0aW9uLCBidXQgb3V0cHV0IG9ubHkgdGhlIGxhc3QgbiBkaWdpdHMgb2YgdGhlIHJlc3VsdC4gRG9pbmcgdGhpcyBlZmZpY2llbnRseSByZXF1aXJlcyBjYXJlZnVsIHRob3VnaHQgYWJvdXQgaG93IHRvIGF2b2lkIGNvbXB1dGluZyB0aGUgZnVsbCBhbnN3ZXIuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGludGVnZXJzIGIsIG4sIGFuZCBpLCB3ZSBkZWZpbmUgdGhlIGZ1bmN0aW9uIGYoeCkgcmVjdXJzaXZlbHkgYnkgZih4KSA9IGI8c3VwPmYoeC0xKTxcL3N1cD4gaWYgeCAmZ3Q7IDAsIGFuZCBmKDApPTEuIFlvdXIgam9iIGlzIHRvIGVmZmljaWVudGx5IGNvbXB1dGUgdGhlIGxhc3QgbiBkZWNpbWFsIGRpZ2l0cyBvZiBmKGkpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIHRoZSBpbnRlZ2VyIGIgKDEgJmx0Oz0gYiAmbHQ7PSAxMDApIGNhbGxlZCB0aGUgYmFzZS4gT24gdGhlIG5leHQgbGluZSBpcyB0aGUgaW50ZWdlciBpICgxICZsdDs9IGkgJmx0Oz0gMTAwKSBjYWxsZWQgdGhlIGl0ZXJhdGlvbiBjb3VudC4gQW5kIGZpbmFsbHksIHRoZSBsYXN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBuICgxICZsdDs9IG4gJmx0Oz0gNyksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGVjaW1hbCBkaWdpdHMgdG8gb3V0cHV0LiBUaGUgaW5wdXQgaXMgdGVybWluYXRlZCB3aGVuIGIgPSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgb24gb25lIGxpbmUgdGhlIGxhc3QgbiBkaWdpdHMgb2YgZihpKSBmb3IgdGhlIGJhc2UgYiBzcGVjaWZpZWQuIElmIHRoZSByZXN1bHQgaGFzIGZld2VyIHRoYW4gbiBkaWdpdHMsIHBhZCB0aGUgcmVzdWx0IHdpdGggemVyb2VzIG9uIHRoZSBsZWZ0IHNvIHRoYXQgdGhlcmUgYXJlIGV4YWN0bHkgbiBkaWdpdHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d