Лягушки
Перед открытием олимпиады членов жюри повезли на экскурсию к водопаду. Но водопад был закрыт на профилактику. После этого зебра Гиппо решила осмотреть окрестности самостоятельно и добралась до знаменитого Длинного Барьерного болота.
Болото представляет собой бесконечно длинную последовательность кочек, занумерованных последовательными неотрицательными целыми числами. Для каждого i ≥ 0 высота кочки i равна остатку от деления x^i на p.
В начальный момент времени k лягушек, занумерованных последовательными целыми числами от 1 до k, находятся на кочке 0, при этом усталость каждой лягушки равна 1. Понаблюдав за лягушками, Гиппо заметила, что лягушки двигаются в соответствии со следующими правилами:
Лягушка с номером 1 двигается на одну кочку вперёд, и её усталость увеличивается на величину, равную высоте новой кочки.
Оставшиеся лягушки двигаются по очереди, начиная со второй, так: i-я лягушка двигается на одну кочку вперёд, если i-1-я лягушка тоже двигалась и усталость i-1-й лягушки делится на m (в этом случае усталость i-й лягушки увеличивается на величину, равную высоте кочки, на которую она попала), иначе она остаётся на месте (и тогда её усталость не меняется).
Если расстояние между первой и k-й лягушками не менее d, лягушки прекращают движение. В противном случае процесс повторяется, начиная с пункта 1.
Вычислите, на какой кочке окажется первая лягушка в момент окончания движения.
Входные данные
Вход содержит пять целых чисел x (1 ≤ x ≤ p-1), p (2 ≤ p ≤ 10^5), k (2 ≤ k ≤ 10), m (2 ≤ m ≤ 10) и d (1 ≤ d ≤ 10^12).
Гарантируется, что число p является простым.
Выходные данные
Выведите номер кочки, на которой окажется первая лягушка в момент, когда лягушки прекратят движение.