초지수승의 마지막 여덟 자리

양의 정수 $a$, $b$에 대해 $a$의 $b$ 초지수승을 $a \uparrow\uparrow b$로 쓴다. 정의는 다음과 같다.

$a \uparrow\uparrow 1 = a$

$a \uparrow\uparrow (k + 1) = a^{(a \uparrow\uparrow k)}$

예를 들어 $3 \uparrow\uparrow 2 = 3^3 = 27$이고, $3 \uparrow\uparrow 3 = 3^{27} = 7625597484987$이다.

$a \uparrow\uparrow b$의 마지막 8자리를 구한다.

첫째 줄에 양의 정수 $a$와 $b$가 공백으로 구분되어 주어진다. ($1 \le a, b \le 20000$)

$a \uparrow\uparrow b$의 마지막 8자리를 한 줄에 출력한다.

$a \uparrow\uparrow b$가 9자리 이상이면 마지막 8자리를 그대로 출력하고, 그 8자리 안에 앞자리 0이 있으면 0도 함께 출력한다. $a \uparrow\uparrow b$가 8자리 이하이면 값 전체를 앞에 0을 붙이지 않고 출력한다.