Problems
Sequence
Sequence
In a sequence of numbers a[1]
, a[2]
, a[3]
, ... the first term is given, and the other terms are calculated using the formula:
a[i]
= (a[i-1]
* a[i-1]
) mod 10000
Find the n-th term of the sequence.
Input data
The first row contains the numbers a[1]
and n (0 ≤ a[1]
≤ 10000, 1 ≤ n ≤ 2000000010).
Output data
Print the value of a[n]
.
Examples
Input example #1
4 3
Output example #1
256
Input example #2
0 2000000000
Output example #2
0