양의 정수 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자리를 출력하시오.

예제 입력

3 3

예제 출력

97484987