Жаби

Перед початком олімпіади членів журі запросили на екскурсію до водоспаду. Однак водоспад був закритий на профілактичні роботи. Тому зебра Гіппо вирішила дослідити околиці самостійно і дісталася до відомого Довгого Бар'єрного болота.

Болото складається з нескінченної послідовності купин, пронумерованих послідовними невід'ємними цілими числами. Для кожного i ≥ 0 висота купини i визначається як залишок від ділення x^i на p.

На початку k жаб, пронумерованих від 1 до k, знаходяться на купині 0, причому втома кожної жаби дорівнює 1. Спостерігаючи за жабами, Гіппо помітила, що вони рухаються за такими правилами:

1. Жаба з номером 1 пересувається на одну купину вперед, і її втома збільшується на величину, що дорівнює висоті нової купини.

2. Інші жаби рухаються по черзі, починаючи з другої: i-та жаба пересувається на одну купину вперед, якщо i-1-ша жаба теж рухалася і її втома ділиться на m (у цьому випадку втома i-ї жаби збільшується на величину, що дорівнює висоті купини, на яку вона потрапила), інакше вона залишається на місці (і тоді її втома не змінюється).

3. Якщо відстань між першою і k-тою жабами стає не меншою за d, жаби припиняють рух. В іншому випадку процес повторюється, починаючи з пункту 1.

Визначте, на якій купині опиниться перша жаба, коли рух припиниться.

Вхідні дані

Вхідні дані містять п'ять цілих чисел x (1 ≤ x ≤ p-1), p (2 ≤ p ≤ 10^5), k (2 ≤ k ≤ 10), m (2 ≤ m ≤ 10) і d (1 ≤ d ≤ 10^12).

Гарантується, що число p є простим.

Вихідні дані

Виведіть номер купини, на якій опиниться перша жаба, коли рух припиниться.

Приклади