Sequence
Easy
Execution time limit is 10 seconds
Runtime memory usage limit is 128 megabytes
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
The first row contains the numbers a[1] and n (0 ≤ a[1] ≤ 10000, 1 ≤ n ≤ 2000000010).
Output
Print the value of a[n].
Examples
Input #1
Answer #1
Input #2
Answer #2
Submissions 4K
Acceptance rate 24%