Задача №671. Последовательность

В последовательности чисел a1, a2, a3, ... задан первый член, а остальные вычисляются по формуле ai = (ai - 1)2 mod 10 000. Найти N-й член последовательности.

Ограничения: 0 <= a1 < 10 000, 1 <= N <= 2 000 000 000.

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

В первой строке находятся числа a1 и N, разделённые пробелом.

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

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

Примеры
Входные данные
6749 2
Выходные данные
9001
Входные данные
6749 1
Выходные данные
6749
Сдать: для сдачи задач необходимо войти в систему