Задача A. K-ая порядковая статистика

Автор:StdAlg   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

K-ой порядковой статистикой N-элементной последовательности AN называется число AK, которое будет стоять на K-ом месте после упорядочивания элементов этой последовательности по возрастанию.

Последовательность AN задаётся следующим образом. A1 = P, Ai = (Ai − 1 ⋅ Q) mod V.

Формат входного файла

Во входном файле содержатся целые числа Q V P N K

Формат выходного файла

В выходном файле должно содержаться единственное число — K-ая порядковая статистика исходной последовательности.

Ограничения

V, Q ≠ 0

0 ≤ Q ⋅ V, Q ⋅ P ≤ 231 − 1

1 ≤ K ≤ N ≤ 4 ⋅ 107

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
343 32767 3 10 7
16478

0.073s 0.015s 13