В последовательности чисел a1, a2, a3, ... задан первый член, а остальные вычисляются по формуле:

ai = (ai-1 * ai-1) mod 10000

Найти n-ый член последовательности.

Входные данные

В первой строке находятся числа a1 и n (0 ≤ a1 ≤ 10000, 1 ≤ n ≤ 2000000010).

Выходные данные

Вывести одно число an.