### Problem Statement

You are given a square board of size NxN. Each 1x1 cell will be colored either black or white. A rectangle on the board is called good if it contains only white cells. A good rectangle is called perfect if it doesn't lie completely within any other good rectangle.

Here's how the board will be colored. You are given ints M, X0, Y0, A, B, C and D. Generate lists X and Y, each of length M, using the following recursive definitions:

X = X0 MOD N

X[i] = (X[i-1]*A+B) MOD N

Y = Y0 MOD N

Y[i] = (Y[i-1]*C+D) MOD N

The board is initially entirely white. Then, for each i, the cell in column X[i] of row Y[i] is colored black. Return the number of perfect rectangles on the board.

### Definition

 Class: PerfectRectangles Method: numberOfRectangles Parameters: int, int, int, int, int, int, int, int Returns: int Method signature: int numberOfRectangles(int N, int M, int X0, int A, int B, int Y0, int C, int D) (be sure your method is public)

### Notes

-The same cell can be painted black multiple times.

### Constraints

-N will be between 1 and 2,000, inclusive.

-M will be between 1 and 4,000,000, inclusive.

-X0,Y0,A,B,C,D will each be between 0 and 2,000, inclusive.

### Examples

0)

 `5` `1` `2` `0` `0` `2` `0` `0`
`Returns: 4`
 One black cell in the center.
1)

 `4` `4` `0` `1` `1` `0` `1` `1`
`Returns: 6`
 Black cells form the diagonal of the square.
2)

 `1` `1000000` `1` `2` `3` `1` `4` `7`
`Returns: 0`
 All cells are black.
3)

 `10` `20` `4` `76` `2` `6` `2` `43`
`Returns: 12`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10171

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13522&pm=10171

Gluk

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

Search