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