Overlaying Domino Arrangements

You are given an n × m board and k domino pieces (each of size 1 × 2) numbered from 1 to k. You are allowed to select any number of pieces with the count between l and r (inclusive). The selected pieces are placed onto the board one by one in increasing order of their numbers. When placing a domino piece, you may choose either a horizontal or vertical placement as long as the two cells it covers are adjacent on the board. Note: A later‐placed domino will cover (i.e. overwrite) any parts of previously placed dominoes.

The final board is given – each cell shows the number of the domino that is visible on that cell (i.e. the domino piece that was placed last covering that cell). A domino piece that is placed might become completely hidden (if both of its cells are overwritten by dominoes with larger numbers) or completely visible (if none of its cells are overwritten).

An arrangement is defined by the following:

• The set of domino pieces chosen (and hence their count);
• The placement (position and orientation) of each domino piece.

Two arrangements are considered identical if and only if the number of pieces selected, the set of domino IDs chosen, and the placement (position and orientation) of each domino piece are exactly the same.

It can be proved that in any valid final board:

• For any domino piece that is visible on the final board, the number appears exactly twice and in two adjacent cells (horizontally or vertically).
• Domino pieces that are not visible were either not chosen or were completely covered by later placements.

Your task is to compute the number of different arrangements that could have produced the given final board configuration, modulo \(10^9+7\).

Input Format: The input begins with five integers n, m, k, l, r. Then follow n lines, each containing m integers – the final board configuration. It is guaranteed that the board is a result of some valid arrangement under the above process.

Note: For any domino piece that appears in the final board, its two occurrences must be adjacent (either horizontally or vertically). For any domino piece that does not appear, if it is placed its placement must be such that both cells covered have final numbers greater than the domino's number (so that they are overwritten by later dominoes).

Hint: A useful approach is to process the domino pieces in increasing order. For domino pieces that appear on the final board, there is exactly 1 valid placement (if the two cells with that number are adjacent). For those that do not appear, you may choose not to place them, or place them arbitrarily in any valid location (a location is valid if both cells have final numbers greater than the domino's number). Finally, you must ensure that the total count of placed dominoes (visible plus invisible) lies between l and r.

inputFormat

The first line contains five space‐separated integers: n (number of rows), m (number of columns), k (total number of domino pieces available), l and r (minimum and maximum number of domino pieces that can be placed).

The next n lines each contain m space‐separated integers describing the final configuration of the board. The integer in each cell represents the domino number visible in that cell.

outputFormat

Output a single integer – the number of valid arrangements that could have produced the given board configuration, modulo \(10^9+7\).

sample

1 2 1 1 1
1 1

1