Задачі
Hard MEX
Hard MEX
\textit{Жарт, повторений двічі, стає зрозумілішим}Микола Фоменко
Після маленької переможної війни, вже відомий нам диктатор Лі Сій Син (див. задачу \href{/problems/5880}{MEX}) розширив свої володіння і тепер у нього в армії стало аж \textbf{P} солдат. Він перенумеровав їх з нуля за спаданням командирських здібностей, після чого репресував \textbf{N} з них. Оскільки \textbf{N} може бути дуже великим, йому було ліньки складати списки вручну. Замість цього він сказав, що першим репресуєт солдата під номером \textbf{x_1}, а далі номер репресованого визначається за таким правилом:
\textbf{x_1 = (a∙x_\{i-1\} + b) mod P}
Тут операція \textbf{mod} позначає взяття остчі при діленні. Не дивуйтесь, якщо хтось був репресований по декілька разів -- Лі Сій Син дуже жорстокий. Тепер він знову хоче вибрати самого талановитого бійця серед тих, що залишились. Допоможіть йому і, може бути, він пощадить Вас!
\InputFile
Перший рядок містить пару чисел \textbf{P} та \textbf{N} (\textbf{1} ≤ \textbf{N} < \textbf{P} ≤ \textbf{10^9}, \textbf{N} ≤ \textbf{10^7}) -- кількість солдат у армії та кількість репресованих. Другий рядок містить \textbf{2} цілих числа \textbf{a} та \textbf{b} (\textbf{0} ≤ \textbf{a}, \textbf{b} ≤ \textbf{10^9}), які задають правила репресій. Третій рядок містить номер першої жертви Лі Сій Сина.
\OutputFile
Виведіть номер самого талановитого серед тих що вижили військових.
Вхідні дані #1
9 5 1 2 1
Вихідні дані #1
2