2 sec, 256 M
We have to work so as not to be excruciatingly painful for our time free of charge.
It is not a secret that the ONU students love to perform laboratory work. They are night and day in the sweat of brow and not sparing the stomach pore over countless puzzles, study hundreds of manuals and produce tons of waste paper reporting with great pleasure. And of course having invested so much effort in the lab, every student wants to be judged on merit. How sometimes it hurt when your lab done brilliantly catches the eye of the teacher who is in a nasty mood and the next day your careless classmate passing a work done on anyhow to the contented Sensei. That is to know in advance what the mood as well! Fortunately, not all processes in the universe are random.
For example, the results of many years of observations students of Concrete Mathematics, a professor’s Varfalamey Gavriilovich Krikushin mood ranges from 0 to p-1 freebie-units. With that, if today the figure is R, then tomorrow it will be equal to R - D. If the result of the subtraction is less than 0, is added to it by p freebie-units for as long as it does not become a non-negative (probably the day Varfalamey Gavriilovich gets salary). You know the mood of Professor Krikushin today, and yet you know for how many days you do your lab. You are very interested in what are your chances of getting a good grade.
Input. The only input line contains 4 integers: R, D, p, n (R is from 0 to p-1, the other numbers are from 1 to 109) – current professor’s mood sentiment, difference between two adjacent days, top (unattainable) professor’s mood limit, the number of days before passing.
Output. Print a single number - the professor’s mood n days later.
|3 1 4 2||1|
|3 2 4 2||3|
Idea – Arthur Leonidovich Maximov
KBIS Software Developer