В последовательности чисел a
1, a
2, a
3, ... задан первый член, а остальные вычисляются по формуле a
i = (a
i - 1)2 mod 10 000. Найти N-й член последовательности.
Ограничения: 0 <= a
1 < 10 000, 1 <= N <= 2 000 000 000.
Входные данные
В первой строке находятся числа a
1 и N, разделённые пробелом.
Выходные данные
Вывести одно число - a
N.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6749 2
|
9001
|
|
2
|
6749 1
|
6749
|