Description

lmh like playing the guitar, but he don’t satisfy others’ GTP. He want to write guitar score by himself. And he don’t want to use $53231323$, it’s boring! He want to find a new rhythm. So he come up with a idea: get a GTP by computer and math. So he choose $“n^k”$ this expression. But we know, the guitar just have only six chords. So we have to change all $7,8,9$ to $1,2,3$($7$ to $1$, $8$ to $2$, $9$ to $3$, $0$ means open string).

Now give you n and k, can you give lmh a prefect GTP?

Format

Input

Input contains multiple test cases.

Each test case starts with two numbers $n$ and $k (0 < N <= 300, 0 < k <= 300).$

Output

Calculate $n^k$ and change all $7,8,9$ to $1,2,3$($7$ to $1$, $8$ to $2$, $9$ to $3$).

Samples

2 2
2 4
2 7

4
16
122