Послідовність

У послідовності чисел a[1], a[2], a[3], ... задано перший член, а інші обчислюються за формулою:

a[i] = (a[i-1] * a[i-1]) mod 10000

Знайти n-ий член послідовності.

Вхідні дані

Перший рядок містить числа a[1] та n (0 ≤ a[1] ≤ 10000, 1 ≤ n ≤ 2000000010).

Вихідні дані

Вивести одне число a[n].

Приклади