Hard MEX#5875
You are given a collection of numbered items, labeled from to P - 1. A process selects (possibly repeated) items from the collection according to the following rule:
The first selected item has number x_1. Each subsequent selected item's number is computed as:
where and are given integers, and denotes the remainder after division. The process can select the same item more than once. After items have been selected, determine the smallest non-negative integer less than that was not selected during the process.
The first line contains two integers and (1 \le N < P \le 10^9, N \le 10^7) — the total number of items and the number of selections.
The second line contains two integers and (0 \le a, b \le 10^9), which define the selection rule.
The third line contains a single integer x_1 — the number of the first selected item.
Output a single integer — the smallest number from to P - 1 that was not selected during the process.
Example 1