시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 65 25 22 40.000%

문제

음이아닌 b진법 정수 p와 m이 주어졌을 때, p를 m으로 나눈 나머지를 b진법으로 구하는 프로그램을 작성하시오.

p를 m으로 나눈 나머지란 임의의 정수 a에 대해서 p = a*m + k를 만족하는 가장 작은 k를 말한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 3개의 정수가 한 줄로 이루어져 있다. 첫 번째 숫자는 b이고, 2보다 크거나 같고, 10보다 작거나 같은 값을 가진다. 두 번째 숫자는 p이고, 세 번째 숫자는 m이다. p와 m은 0과 b-1사이의 수로만 이루어져 있고, p의 최대 길이는 1000, m의 최대 길이는 9이다.

마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, p를 m으로 나눈 나머지를 b진법으로 출력한다.

예제 입력 1

2 1100 101
10 123456789123456789123456789 1000
0

예제 출력 1

10
789

힌트

W3sicHJvYmxlbV9pZCI6IjQzMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMzBcdWNkMDggXHViMDk4XHViYTM4XHVjOWMwIFx1YWNjNFx1YzBiMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzRjXHVjNzc0XHVjNTQ0XHViMmNjIGJcdWM5YzRcdWJjOTUgXHVjODE1XHVjMjE4IHBcdWM2NDAgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBwXHViOTdjIG1cdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBiXHVjOWM0XHViYzk1XHVjNzNjXHViODVjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5wXHViOTdjIG1cdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjc4MCBcdWM3ODRcdWM3NThcdWM3NTggXHVjODE1XHVjMjE4IGFcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIHAgPSBhKm0gKyBrXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIGtcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCAzXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IGJcdWM3NzRcdWFjZTAsIDJcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWFjMTJcdWM3NDQgXHVhYzAwXHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBwXHVjNzc0XHVhY2UwLCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBtXHVjNzc0XHViMmU0LiBwXHVjNjQwIG1cdWM3NDAgMFx1YWNmYyBiLTFcdWMwYWNcdWM3NzRcdWM3NTggXHVjMjE4XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIHBcdWM3NTggXHVjZDVjXHViMzAwIFx1YWUzOFx1Yzc3NFx1YjI5NCAxMDAwLCBtXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFlMzhcdWM3NzRcdWIyOTQgOVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBwXHViOTdjIG1cdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBiXHVjOWM0XHViYzk1XHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MzI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFzaWMgcmVtYWlucyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBiYXNlIGIgYW5kIHR3byBub24tbmVnYXRpdmUgYmFzZSBiIGludGVnZXJzIHAgYW5kIG0sIGNvbXB1dGUgcCBtb2QgbSBhbmQgcHJpbnQgdGhlIHJlc3VsdCBhcyBhIGJhc2UgYiBpbnRlZ2VyLiBwIG1vZCBtIGlzIGRlZmluZWQgYXMgdGhlIHNtYWxsZXN0IG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIGsgc3VjaCB0aGF0IHAgPSBhKm0gKyBrIGZvciBzb21lIGludGVnZXIgYS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIGNhc2VzLiBFYWNoIGNhc2UgaXMgcmVwcmVzZW50ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdGhyZWUgdW5zaWduZWQgaW50ZWdlcnMuIFRoZSBmaXJzdCwgYiwgaXMgYSBkZWNpbWFsIG51bWJlciBiZXR3ZWVuIDIgYW5kIDEwLiBUaGUgc2Vjb25kLCBwLCBjb250YWlucyB1cCB0byAxMDAwIGRpZ2l0cyBiZXR3ZWVuIDAgYW5kIGItMS4gVGhlIHRoaXJkLCBtLCBjb250YWlucyB1cCB0byA5IGRpZ2l0cyBiZXR3ZWVuIDAgYW5kIGItMS4gVGhlIGxhc3QgY2FzZSBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyAwPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgYSBsaW5lIGdpdmluZyBwIG1vZCBtIGFzIGEgYmFzZS1iIGludGVnZXI8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d