Siêu mũ của số ~a~ bởi một số nguyên dương ~b~, kí hiệu là ~a ^{\wedge \wedge} b~ được xác định như sau:

~a ^{\wedge \wedge} 1 = a~,

~a ^{\wedge \wedge} (k+1) = a ^ {(a ^{\wedge \wedge} k)} ~

Do đó ta có ví dụ:

~ 3^{\wedge \wedge} 2 = 3^3 = 27~, như vậy ~3 ^ {\wedge \wedge} 3 = 3^{27} = 7625597484987~

Tìm ~8~ chữ số cuối cùng của ~a~.

Input

Gồm nhiều test, mỗi test gồm ~2~ số nguyên ~a~ và ~b \leq 20000~

Output

Với mỗi test, in ra kết quả phải tìm.

Sample Input

3 3

Sample Output

97484987