Last eight digits of a power tower

Time limit1sMemory limit256 MB

Summary

Given a and b, print the last eight digits of the b-level power tower of a, keeping leading zeros for large values.

Level: Hard8 of 10
Topics: Number theory, Math, Recursion
Solved: No attempts yet

Problem

For positive integers $a$ and $b$ , write the $b$ -th power tower of $a$ as $a \uparrow\uparrow b$ . It is defined by

$a \uparrow\uparrow 1 = a$

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

For example, $3 \uparrow\uparrow 2 = 3^3 = 27$ and $3 \uparrow\uparrow 3 = 3^{27} = 7625597484987$ .

Find the last 8 digits of $a \uparrow\uparrow b$ .

Input

The first line contains two positive integers $a$ and $b$ , separated by a space. ( $1 \le a, b \le 20000$ )

Output

Print the last 8 digits of $a \uparrow\uparrow b$ on one line.

If $a \uparrow\uparrow b$ has 9 or more digits, print those last 8 digits exactly, including any zeros at the front of them. If $a \uparrow\uparrow b$ has 8 or fewer digits, print the whole value without adding leading zeros.

Examples7

Example 1
Input
```
3 3
```
Expected output
```
97484987
```
Example 2
Input
```
1 20000
```
Expected output
```
1
```
Example 3
Input
```
2 2
```
Expected output
```
4
```
Example 4
Input
```
20000 1
```
Expected output
```
20000
```
Example 5
Input
```
8 2
```
Expected output
```
16777216
```
Example 6
Input
```
9 2
```
Expected output
```
87420489
```
Example 7
Input
```
2 4
```
Expected output
```
65536
```