Sequenza#1083

Sequenza

10 secondi
128 megabyte
Facile

In una data sequenza numerica a_1, a_2, a_3, \ldots è noto il primo termine, e ogni termine successivo viene calcolato secondo la seguente formula:

a_i = (a_{i-1} \cdot a_{i-1}) \bmod 10000.

Trovate l'-esimo termine di questa sequenza.

Input

Nella prima riga sono forniti due numeri interi: a_1 e (0 \leq a_1 \leq 10000, 1 \leq n \leq 2000000010).

Output

Stampate un numero intero a_n.

Esempi

Esempio 1

Loading
Loading