K-th Element
Турнир за Купата на Декана, 2012
Time Limit: 1s, Memory Limit: 128MiB
Ели и Станчо получиха своята първа поръчка! Техният клиент има специфични изисквания за степента на минерализираност на водата – той иска точно K-тия по минерализираност тип от водите, които те предлагат.

Компанията на Ели и Станчо предлага N вида минерална вода, всеки от които има дадена степен на минерализираност (като е възможно повече от един вид да имат еднаква степен). Поради странния начин на производство, първият вид има стойност F, а всеки следващ се образува от предходния, като той е умножен по някаква константа A, след това е прибавено B и накрая е взет остатъка от резултата, при деление на M. Тоест, стойностите на минерализираност на водата, която предлагат, е редицата V1, V2, ..., VN, като:
  • V1 = F
  • V2 = (V1 * A + B) % M
  • V3 = (V2 * A + B) % M
  • ...
  • VN = (VN-1 * A + B) % M
Помогнете на Ели да намери колко минерализиран е K-тият по стойност на минерализираност вид много бързо. За да мине програмата ви ще трябва да измислите по-добро от O(N * log(N)) решение!
Вход
На единствен ред на стандартния вход ще бъдат зададени шест цели числа, разделени с интервал – K, N, F, A, B, M – позицията на търсения елемент, както и параметрите за генерирането на мултимножеството.
Изход
На стандартния изход изведете едно цяло число – стойността на К-тия по големина елемент от мултимножеството.
Ограничения
  • 1 ≤ KN ≤ 20,000,000
  • 1 ≤ F, A, B < M ≤ 2,000,000,000
Примерен Вход Примерен Изход
5 7 3 3 1 2011
133742 666666 13 17 1 1000003199858
В първия пример образуваната редица е {3, 10, 11, 14, 3, 10, 11}. Петият по големина елемент в нея е със стойност 11.
Мрън!