시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 81 26 18 37.500%

문제

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

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+Zih4LTEpPFwvc3VwPiAoeCZndDswKSwgZigwKSA9IDFcdWI4NWMgXHVjODE1XHVjNzU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBmKGkpXHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBuXHVjNzkwXHViOWFjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjMTM4IFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGIoMSAmbGU7IGIgJmxlOyAxMDApLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGkoMSAmbGU7IGkgJmxlOyAxMDApLCBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG4oMSAmbGU7IG4gJmxlOyA3KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgZihpKVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5Yzkgblx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjYjBcdWFjZmNcdWFjMDAgblx1Yzc5MFx1YjlhY1x1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDQgXHViNTRjXHViMjk0LCBcdWM1NWVcdWM1ZDAgMFx1Yzc0NCBcdWNjNDRcdWM2Y2Mgblx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWI5ZGVcdWNkOTggXHViNGE0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ4NjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMYXN0IERpZ2l0cyIsImRlc2NyaXB0aW9uIjoiPHA+RXhwb25lbnRpYXRpb24gb2Ygb25lIGludGVnZXIgYnkgYW5vdGhlciBvZnRlbiBwcm9kdWNlcyB2ZXJ5IGxhcmdlIHJlc3VsdHMuIEluIHRoaXMgcHJvYmxlbSwgd2Ugd2lsbCBjb21wdXRlIGEgZnVuY3Rpb24gYmFzZWQgb24gcmVwZWF0ZWQgZXhwb25lbnRpYXRpb24sIGJ1dCBvdXRwdXQgb25seSB0aGUgbGFzdCBuIGRpZ2l0cyBvZiB0aGUgcmVzdWx0LiBEb2luZyB0aGlzIGVmZmljaWVudGx5IHJlcXVpcmVzIGNhcmVmdWwgdGhvdWdodCBhYm91dCBob3cgdG8gYXZvaWQgY29tcHV0aW5nIHRoZSBmdWxsIGFuc3dlci48XC9wPlxyXG5cclxuPHA+R2l2ZW4gaW50ZWdlcnMgYiwgbiwgYW5kIGksIHdlIGRlZmluZSB0aGUgZnVuY3Rpb24gZih4KSByZWN1cnNpdmVseSBieSBmKHgpID0gYjxzdXA+Zih4LTEpPFwvc3VwPiBpZiB4ICZndDsgMCwgYW5kIGYoMCk9MS4gWW91ciBqb2IgaXMgdG8gZWZmaWNpZW50bHkgY29tcHV0ZSB0aGUgbGFzdCBuIGRlY2ltYWwgZGlnaXRzIG9mIGYoaSkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggdGhlIGludGVnZXIgYiAoMSAmbHQ7PSBiICZsdDs9IDEwMCkgY2FsbGVkIHRoZSBiYXNlLiBPbiB0aGUgbmV4dCBsaW5lIGlzIHRoZSBpbnRlZ2VyIGkgKDEgJmx0Oz0gaSAmbHQ7PSAxMDApIGNhbGxlZCB0aGUgaXRlcmF0aW9uIGNvdW50LiBBbmQgZmluYWxseSwgdGhlIGxhc3QgbGluZSBjb250YWlucyB0aGUgbnVtYmVyIG4gKDEgJmx0Oz0gbiAmbHQ7PSA3KSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkZWNpbWFsIGRpZ2l0cyB0byBvdXRwdXQuIFRoZSBpbnB1dCBpcyB0ZXJtaW5hdGVkIHdoZW4gYiA9IDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBvbiBvbmUgbGluZSB0aGUgbGFzdCBuIGRpZ2l0cyBvZiBmKGkpIGZvciB0aGUgYmFzZSBiIHNwZWNpZmllZC4gSWYgdGhlIHJlc3VsdCBoYXMgZmV3ZXIgdGhhbiBuIGRpZ2l0cywgcGFkIHRoZSByZXN1bHQgd2l0aCB6ZXJvZXMgb24gdGhlIGxlZnQgc28gdGhhdCB0aGVyZSBhcmUgZXhhY3RseSBuIGRpZ2l0cy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==