John's friend Peter purchases a new high resolution monitor with dimension W * H where W is the number of pixels in each row (i.e. width) and H is the number of pixels in each column (i.e. height).
However, there are N dead pixels on the monitor. The i-th dead pixel is located at (x[i], y[i]). (0, 0) is the top-left pixel and (W - 1, H - 1) is the bottom-right pixel. The locations of the dead pixels could be generated by 6 given integers X, Y, a, b, c and d by the following rules. If 2 pixels are at the same location, they are considered the same. It is possible that there are less than N distinct dead pixels.
- x[0] = X
- y[0] = Y
- x[i] = (x[i - 1] * a + y[i - 1] * b + 1) % W (for 0 < i < N)
- y[i] = (x[i - 1] * c + y[i - 1] * d + 1) % H (for 0 < i < N)
Peter connects his monitor to his computer and opens an image with dimension P (width) * Q (height). How many unique positions can the image be placed so that it can be displayed perfectly (i.e. all pixels of the picture are shown on the monitor)? The ima