Competitions

# Exponentiation

# Sequence

In a sequence of numbers `a`

, _{1}`a`

, _{2}`a`

, ... the first term is given, and the other terms are calculated using the formula:_{3}

`a`

= (_{i}`a`

* _{i-1}`a`

) mod _{i-1}**10000**

Find the **n**-th term of the sequence.

#### Input

The first row contains the numbers `a`

and _{1}**n** (**0** ≤ `a`

≤ _{1}**10000**, **1** ≤ **n** ≤ **2000000010**).

#### Output

Print the value of `a`

._{n}

Input example #1

4 3

Output example #1

256

Input example #2

0 2000000000

Output example #2

0