16 digits#3707
Sign in

16 digits

1 second
256 megabytes
Very easy

Find the 16 last digits of the number a_n, where the sequence a_n is defined recursively as follows:

\begin{align*} a_1 &= p, \\ a_n &= p^{a_{n-1}}, \quad n > 1. \end{align*}

Input

Two integers and are given as input (7 \le p \le 100, 1 \le n \le 100), where is a prime number.

Output

Output the remainder of a_n divided by 10^{16}, without leading zeros in the result.

Examples

Example 1

Loading
Loading