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