Problem Description

The Up-up of a number a by a positive integer b, denoted by a↑↑b, is recursively defined by:
a↑↑1 = a,
a↑↑(k+1) = a ^(a↑↑k)
Thus we have e.g. 3↑↑2 = 3³ = 27, hence 3↑↑3 = 3²⁷= 7625597484987 and 3↑↑4 is roughly 10^{3.6383346400240996*10^12}
The problem is give you a pair of a and k,you must calculate a↑↑k ,the result may be large you can output the answer mod 100000000 instead

Input

A pair of a and k .a is a positive integer and fit in __int64 and 1<=k<=200

Output

a↑↑k mod 100000000

3 2
3 3

27
97484987