Finding the Reading Day

Little W has a new book with \(p\) pages, numbered from \(0\) to \(p-1\). He is too busy to read more than one page a day. In order to make his reading schedule more interesting, he decides to use the linear congruential method he learned at NOI2012 to generate a sequence which will determine the page he reads each day.

The sequence \(\{x_i\}\) is generated using three parameters \(a\), \(b\), and \(x_1\) (all integers satisfying \(0 \le a, b, x_1 < p\)) according to the following recurrence relation:

[ x_{i+1} \equiv a \times x_i + b \pmod{p} ]

However, this method might result in reading the same page on different days. Little W wants to know the earliest day on which he will read page \(t\). If page \(t\) is never read, output \(-1\).

inputFormat

The input consists of a single line containing five space-separated integers:

• \(p\) (the number of pages in the book),
• \(a\) and \(b\) (the parameters of the linear congruential generator),
• \(x_1\) (the first generated number), and
• \(t\) (the target page number).

It is guaranteed that \(0 \leq a, b, x_1, t < p\).

outputFormat

Output a single integer, which is the earliest day (starting with day 1 for \(x_1\)) on which page \(t\) is read. If page \(t\) is never read, output \(-1\).

sample

10 1 1 2 5

4