시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 163 27 9 15.254%

문제

양의 정수 a, b에 대해서, a의 b 초지수승은 a ↑↑ b와 같이 나타낸다. 초지수승의 정의는 다음과 같다.

a ↑↑ 1 = a,

a ↑↑ (k + 1) = a ^ (a ↑↑ k)

따라서 예를 들면, 3↑↑2 = 3^3 = 27 이고, 3↑↑3 = 3^27 = 7625597484987이다.

a ↑↑ b의 마지막 8자리를 출력하세요.

입력

양의 정수 a, b가 입력된다. (a, b ≤ 20000)

출력

a ↑↑ b의 마지막 8자리를 출력하시오.

예제 입력 1

3 3

예제 출력 1

97484987
W3sicHJvYmxlbV9pZCI6IjExMDMwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiU1VQRVIgSEFUUyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgYVx1Yzc1OCBiJm5ic3A7XHVjZDA4XHVjOWMwXHVjMjE4XHVjMmI5XHVjNzQwJm5ic3A7YSAmdWFycjsmdWFycjsgYlx1YzY0MCBcdWFjMTlcdWM3NzQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWNkMDhcdWM5YzBcdWMyMThcdWMyYjlcdWM3NTggXHVjODE1XHVjNzU4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmEgJnVhcnI7JnVhcnI7IDEgPSBhLDxcL3A+XHJcblxyXG48cD5hICZ1YXJyOyZ1YXJyOyAoayArIDEpID0gYSBeJm5ic3A7KGEgJnVhcnI7JnVhcnI7IGspPFwvcD5cclxuXHJcbjxwPlx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCZuYnNwOzMmdWFycjsmdWFycjsyID0gM14zID0gMjcgXHVjNzc0XHVhY2UwLCAzJnVhcnI7JnVhcnI7MyA9IDNeMjcgPSZuYnNwOzc2MjU1OTc0ODQ5ODdcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmEgJnVhcnI7JnVhcnI7IGJcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IDhcdWM3OTBcdWI5YWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMTM4XHVjNjk0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiXHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4mbmJzcDsoYSwmbmJzcDtiICZsZTsgMjAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+YSAmdWFycjsmdWFycjsgYlx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgOFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTEwMzAiLCJwcm9ibGVtX2xhbmciOiI2IiwidGl0bGUiOiJTSVx1MDBjYVUgTVx1MDE2OCIsImRlc2NyaXB0aW9uIjoiPHA+U2kmZWNpcmM7dSBtXHUwMTY5IGNcdTFlZTdhIHNcdTFlZDEgYSBiXHUxZWRmaSBtXHUxZWQ5dCBzXHUxZWQxIG5ndXkmZWNpcmM7biBkXHUwMWIwXHUwMWExbmcgYiwgayZpYWN1dGU7IGhpXHUxZWM3dSBsJmFncmF2ZTsgYSZ1YXJyOyZ1YXJyO2IgaG9cdTFlYjdjIGwmYWdyYXZlOyA8c3VwPmI8XC9zdXA+YSwgXHUwMTExXHUwMWIwXHUxZWUzYyB4JmFhY3V0ZTtjIFx1MDExMVx1MWVjYm5oIG5oXHUwMWIwIHNhdTo8XC9wPlxyXG5cclxuPHA+YSZ1YXJyOyZ1YXJyOzEgPSBhLCZuYnNwOzxcL3A+XHJcblxyXG48cD5hJnVhcnI7JnVhcnI7KGsrMSkgPSBhPHN1cD4oYSZ1YXJyOyZ1YXJyO2spPFwvc3VwPjxcL3A+XHJcblxyXG48cD5EbyBcdTAxMTEmb2FjdXRlOyB0YSBjJm9hY3V0ZTsgdiZpYWN1dGU7IGRcdTFlZTU6IDMmdWFycjsmdWFycjsyID0gMzxzdXA+MzxcL3N1cD4gPSAyNywgbmhcdTAxYjAgdlx1MWVhZHkgMzxzdXA+MzxcL3N1cD4gPSAzPHN1cD4yNzxcL3N1cD4gPSA3NjI1NTk3NDg0OTg3PFwvcD5cclxuXHJcbjxwPlQmaWdyYXZlO20gOCBjaFx1MWVlZiBzXHUxZWQxIGN1XHUxZWQxaSBjJnVncmF2ZTtuZyBjXHUxZWU3YSBhJnVhcnI7JnVhcnI7Yi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkdcdTFlZDNtIG5oaVx1MWVjMXUgdGVzdCwgbVx1MWVkN2kgdGVzdCBnXHUxZWQzbSAyIHNcdTFlZDEgbmd1eSZlY2lyYztuIGEgdiZhZ3JhdmU7IGIgJmxlOyAyMDAwMDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlZcdTFlZGJpIG1cdTFlZDdpIHRlc3QsIGluIHJhIGtcdTFlYmZ0IHF1XHUxZWEzIHBoXHUxZWEzaSB0JmlncmF2ZTttPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHViY2EwXHVkMmI4XHViMGE4XHVjNWI0In1d