Ели и Станчо получиха своята първа поръчка! Техният клиент има специфични изисквания за степента на минерализираност на водата – той иска точно K-тия по минерализираност тип от водите, които те предлагат.

Компанията на Ели и Станчо предлага N вида минерална вода, всеки от които има дадена степен на минерализираност (като е възможно повече от един вид да имат еднаква степен). Поради странния начин на производство, първият вид има стойност F, а всеки следващ се образува от предходния, като той е умножен по някаква константа A, след това е прибавено B и накрая е взет остатъка от резултата, при деление на M. Тоест, стойностите на минерализираност на водата, която предлагат, е редицата V₁, V₂, ..., V_N, като:

• V₁ = F
• V₂ = (V₁ * A + B) % M
• V₃ = (V₂ * A + B) % M
• ...
• V_N = (V_N-1 * A + B) % M

Помогнете на Ели да намери колко минерализиран е K-тият по стойност на минерализираност вид много бързо. За да мине програмата ви ще трябва да измислите по-добро от O(N * log(N)) решение! На единствен ред на стандартния вход ще бъдат зададени шест цели числа, разделени с интервал – K, N, F, A, B, M – позицията на търсения елемент, както и параметрите за генерирането на мултимножеството. На стандартния изход изведете едно цяло число – стойността на К-тия по големина елемент от мултимножеството.

• 1 ≤ K ≤ N ≤ 20,000,000
• 1 ≤ F, A, B < M ≤ 2,000,000,000

Примерен Вход	Примерен Изход
5 7 3 3 1 20	11
133742 666666 13 17 1 1000003	199858