Региональная студенческая предметная олимпиада по информатике (предмет) 2017 г.

Соревнование завершилось 09.04.17 в 16:00

B. Шифр (75 баллов)

Ограничение по времени: 1 с.
Ограничение по памяти: 256 МБ

Лёня и Лена хотят делиться секретами друг с другом. А общаются они в чате, который читают все, кому не лень. Они придумали способ шифровать свои сообщения так, что, имея ключ шифрования, они могут как шифровать, так и расшифровывать сообщения друг друга. В качестве ключа шифрования может быть любое число, не известное никому, кроме них двоих.

Теперь встаёт проблема: как им придумать такое число, чтобы его знали только они вдвоём, с учётом того, что договариваться они могут только в чате, который читают все, кому не лень.

Лёня предложил такой способ: он придумает два числа e и C и отправит их Лене в общем чате. Далее он придумает число A, и Лене в общем чате отправит e^A \mod C. Лена придумает число B и отправит Лёне в ответ число e^B \mod C. Таким образом, в общем чате никто не узнает чисел A и B. Теперь Лёня возьмет число e^B \mod C (которое прислала Лена) и вычислит (e^B)^A \mod C. Лена же возьмет число, которое прислал Лёня и вычислит (e^A)^B \mod C. И их ключом шифрования будет число e^{A \cdot B} \mod C.

Осталась одна задача — научиться вычислять X^Y \mod Z для некоторых чисел X, Y и Z.

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

В первой строке входного потока находится одно число X (0 < X < 10^{1000}).

Во второй строке входного потока находится одно число Y (0 < Y < 10^{1000}).

В третьей строке входного потока находится одно простое число Z (1 < Z < (10^{17} - 1) \cdot 10).

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

В единственной строке выходного потока должен находиться остаток отделения X^Y на Z.

Примеры
Стандартный вводСтандартный вывод
140
845
1280606429
711004570
2
3
5
3
Примечания

Под записью X \mod Z понимается остаток от деления X на Z.