Qurbağalar
Olimpiadanın açılış mərasimindən əvvəl münsiflər heyəti şəlaləyə ekskursiyaya aparıldı. Lakin şəlalə texniki baxış üçün bağlı idi. Bu vəziyyətdən sonra zebra Hippo ətrafı təkbaşına araşdırmağa qərar verdi və məşhur Uzun Maneə bataqlığına gəldi.
Bataqlıq sonsuz uzunluqda, ardıcıl qeyri-mənfi tam ədədlərlə nömrələnmiş qabarıq bir sıra təşkil edir. Hər bir i ≥ 0 üçün i-ci qabarığın hündürlüyü x^i ədədi p-yə bölünəndə qalan qalığa bərabərdir.
Başlanğıcda k ədəd qurbağa, ardıcıl tam ədədlərlə 1-dən k-ya qədər nömrələnmiş, 0-cı qabarığın üzərindədir və hər bir qurbağanın yorğunluğu 1-ə bərabərdir. Qurbağaları müşahidə edən Hippo gördü ki, qurbağalar aşağıdakı qaydalara uyğun hərəkət edirlər:
1 nömrəli qurbağa bir qabarıq irəli hərəkət edir və onun yorğunluğu yeni qabarığın hündürlüyü qədər artır.
Qalan qurbağalar növbə ilə, ikincidən başlayaraq belə hərəkət edir: i-ci qurbağa bir qabarıq irəli hərəkət edir, əgər i-1-ci qurbağa da hərəkət edibsə və i-1-ci qurbağanın yorğunluğu m-ə bölünürsə (bu halda i-ci qurbağanın yorğunluğu onun düşdüyü qabarığın hündürlüyü qədər artır), əks halda o yerində qalır (və bu zaman onun yorğunluğu dəyişmir).
Əgər birinci və k-cı qurbağalar arasındakı məsafə d-dən az deyilsə, qurbağalar hərəkəti dayandırır. Əks halda proses 1-ci bənddən başlayaraq təkrarlanır.
Hərəkət dayandığı anda birinci qurbağanın hansı qabarığın üzərində olacağını hesablayın.
Giriş verilənləri
Girişdə beş tam ədəd var: x (1 ≤ x ≤ p-1), p (2 ≤ p ≤ 10^5), k (2 ≤ k ≤ 10), m (2 ≤ m ≤ 10) və d (1 ≤ d ≤ 10^12).
p ədədinin sadə olduğu təmin edilir.
Çıxış verilənləri
Qurbağaların hərəkəti dayandırdığı anda birinci qurbağanın üzərində olacağı qabarığın nömrəsini çıxarın.