### Problem Statement

Petya likes donuts. He tries to find them everywhere. For example if he is given a grid where each cell contains a '0' or '.' he will construct donuts from the cells.

To make the donuts:

1. Petya first selects a rectangle of cells of width, w, and height, h, where both are at least 3.
2. Then he removes a rectangular hole of width w-2 and height h-2 centered in the larger rectangle.
3. For the remaining cells (a closed rectangular ring) to be a valid donut, all of the cells must contain '0' (because donuts are shaped like zeros). Cells in the hole can contain anything since they are not part of the donut.

Here is an example with three overlapping donuts.

```..........
.00000000.
.0......0.
.0.000000.
.0.0...00.
.0.0...00.
.0.000000.
.0......0.
.00000000.
..........
```

The grid in this problem will be pseudo-randomly generated using the following method:

You are given four ints: H (the grid height), W (the grid width), seed and threshold. Let x0=seed and for all i>=0 let xi+1 = (xi * 25173 + 13849) modulo 65536. Process the cells of the matrix in row major order (i.e., first row left to right, second row left to right, etc.). Each time you process a cell, calculate the next xi (starting with x1 for the upper left corner). If it is greater than or equal to threshold, the current cell will contain a '.', otherwise it will contain a '0'.

Return the number of distinct donuts in the figure. Two donuts are considered distinct if they either have different width or height, or if the top left hand corner is in a different location (i.e., overlapping donuts are counted).

### Definition

 Class: DonutsOnTheGrid Method: calc Parameters: int, int, int, int Returns: long Method signature: long calc(int H, int W, int seed, int threshold) (be sure your method is public)

### Notes

-The random generation of the input is only for keeping the input size small. The author's solution does not depend on any properties of the generator, and would work fast enough for any input of allowed dimensions.

### Constraints

-H will be between 1 and 350, inclusive.
-W will be between 1 and 350, inclusive.
-seed will be between 0 and 65535, inclusive.
-threshold will be between 0 and 65536, inclusive.

### Examples

0)

 `5` `5` `222` `55555`
`Returns: 4`
 Here is an example of the grid: ```00000 00.0. .0000 00.00 00000```
1)

 `5` `6` `121` `58000`
`Returns: 3`
 Here is the grid and three donuts in it: ```00000. XXX... XXX... ..XXX. 0.0000 X.X... X.X... ..X.X. 0.000. X.X... X.X... ..XXX. 000.00 XXX... X.X... ...... 000.00 ...... XXX... ...... ```
2)

 `4` `5` `6` `50000`
`Returns: 1`
 The grid is: ```0.0.0 00000 .00.0 0.000 ```
3)

 `4` `4` `1` `65536`
`Returns: 9`
 Here, the grid is completely filled by 0's. There are 9 possible placements of a donut: ```XXX. XXX. .XXX .XXX .... .... XXXX .... XXXX X.X. X.X. .X.X .X.X XXX. .XXX X..X XXXX X..X XXX. X.X. .XXX .X.X X.X. .X.X XXXX X..X X..X .... XXX. .... .XXX XXX. .XXX .... XXXX XXXX ```

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14179&pm=10717

K.A.D.R

#### Testers:

Rustyoldman , timmac , StevieT , maksay , K.A.D.R , Seyaua

#### Problem categories:

Dynamic Programming, Simple Search, Iteration