Counting Valid Flood Configurations

Consider a square region divided into an N×N grid. In each cell, the ground elevation is a constant integer between 0 and M. The region is surrounded by infinitely high walls. Over the years, hydrologists have observed some important rules about water accumulation:

1. Each cell is either completely dry or filled with water. If a cell is filled, then the water surface (which is flat within that cell) is an integer strictly greater than the ground elevation in that cell.
2. If water is present in a cell, its water surface level is an integer in the range \(0 \leq w \leq m\) (where m is given) and must satisfy \(w > \text{ground}\).
3. For any two cells sharing a common edge, there must not be a situation that can trigger water flow. In other words, it cannot be that both adjacent cells have water with different water levels, nor can it be that a water‐filled cell has a water level greater than the ground elevation of its adjacent dry cell.

In each water‐filled cell, if it belongs to a connected group (via edge‐adjacency) of water cells, then all cells in that connected component must share the same water level. For a connected water component, let \(L\) be defined as the maximum of \(\text{ground}_{ij}+1\) over all cells in that component. Also, if a water cell in the component has a dry neighbor (inside the grid), then the water level \(w\) must satisfy \(w \leq \text{ground}_{\text{dry}}\). Formally, if the minimum ground elevation among all dry neighbors of the component is \(G\), then \(w\) must satisfy \(L \leq w \leq \min(m, G)\) (if the component touches no dry cell inside the grid, then \(w \leq m\)).

You are given the grid of ground elevations. Determine the total number of distinct water configurations (including both the decision of which cells are water‐filled and the specific water level choices for each connected water region) that satisfy the above rules. Note that a configuration where all cells are dry is considered valid.

inputFormat

The first line contains three integers: N, M, and m, where N is the grid size, the ground elevation of each cell is between 0 and M, and the water level (if present) is an integer in [0, m].

Then follow N lines, each containing N integers, representing the ground elevations of the grid cells.

outputFormat

Output a single integer – the total number of valid water configurations.

sample

1 5 5
3

3