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