Observations

First, we must determine which integers are in the set of achievable MEX values of the given grid.

In order for an integer ~k~ to be in the set of achievable MEX values, there must exist a subgrid of the given grid whose MEX is equal to ~k~. In other words, there must exist a subgrid which contains all the integers from ~0~ to ~k-1~ but must not include ~k~.

Notice that if such a subgrid exists, then the minimal subgrid containing the integers ~0~ to ~k-1~ will also be a valid subgrid. In other words, it is always optimal to consider the minimal subgrid containing the integers ~0~ to ~k-1~, and checking if ~k~ falls outside of it.

Formally, if ~r_i~ and ~c_i~ denote the row and column number of the integer ~i~ in the given grid, then the value ~k~ is in the set of achievable MEX values if and only if $$\displaystyle r_k < \min_{j<k}(r_j)~ \text{ or } ~r_k > \max_{j<k}(r_j)~ \text{ or } ~c_k < \min_{j<k}(c_j)~ \text{ or } ~c_k > \max_{j<k}(c_j)$$

Another way to interpret this condition is if when adding the elements in the grid in order of increasing value, ~k~ is in the set of achievable MEX values if and only if the minimal rectangle containing the inserted elements is expanded when ~k~ is inserted.

Thus, we can compute whether or not each value belongs to the set of achievable MEX values in ~\mathcal{O}(NM)~ time.

Subtask 1

In this subtask, ~N = 1~. Thus, the grid can be interpreted as an array of length ~M~.

Using our initial observations, we can first determine which integers are in the set of achievable MEX values of the given grid.

To count the number of grids which have the same set of achievable MEX values, we consider counting the number of ways to build the permutation when adding the elements of the grid in order of increasing value.

We first initialize our answer as ~1~, as there is only one way to place the element ~0~ into an empty array. Then, we iterate over the values of ~k~ from ~1~ to ~NM-1~. When inserting the value ~k~ there are two cases:

1. ~k~ is in the set of achievable MEX values.

   • In this case, ~k~ must be to the left of all previously inserted values, or to the right of all previously inserted values.
   • Thus, we multiply our answer by ~2~.

2. ~k~ is not in the set of achievable MEX values.

   • In this case, ~k~ must not expand the subarray containing all previously inserted values.
   • In other words, ~k~ must be placed in bewteen two previously inserted elements.
   • Since ~k~ elements have already been inserted, there are ~k-1~ "gaps" where ~k~ can be placed.
   • Thus, we multiply our answer by ~k-1~.

If we modulo our answer variable by ~10^9+7~ every time we multiply, this provides a ~\mathcal{O}(M)~ solution.

Time Complexity: ~\mathcal{O}(M)~

Subtask 2

This subtask was meant to reward solutions which performed an ~\mathcal{O}(NM)~ transition for all ~NM~ values, as well as other suboptimal implementations of the full solution.

Time Complexity: ~\mathcal{O}(N^2 M^2)~

Subtask 3

For the full solution, we take advantage of the fact that there are at most ~N+M~ achievable MEX values, since the minimal rectangle containing the values ~0,1,\dots,k~ can only expand at most ~N+M-2~ times. We can use combinatorics to skip over the calculations for values which are not in the set of achievable MEX values.

Let ~s[i]~ be the ~i^{th}~ achievable MEX value in increasing order with 0-indexing. In particular, ~s[0] = 0~ and ~s[1] = 1~. (Ruling out the trivial case of ~N = M = 1~).

Let ~dp[k][i][j]~ be the number of ways to place the values ~0,1,\dots,s[k]-1~ such that all of them correctly belong or do not belong to the set of achievable MEX values and they all fit within a ~i \times j~ grid.

The base case is ~dp[1][1][1] = 1~, as there is only ~1~ way to place ~0~ into a ~1 \times 1~ grid.

To compute ~dp[k][i][j]~, we must have already inserted the values ~0,1,\dots,s[k-1]-1~ into a rectangle with dimensions smaller than ~i \times j~, so that when inserting ~s[k-1]~, the minimal rectangle containing the inserted values is expanded to dimensions ~i \times j~ (and thus ~s[k-1]~ would be in the set of achievable MEX values).

Let the dimensions of the minimal rectangle before inserting ~s[k-1]~ be ~i' \times j'~. By our recurrence, there are ~dp[k-1][i'][j']~ ways to insert the values ~0, 1, \dots, s[k-1]-1~ such that all of them correctly belong or do not belong to the set of achievable MEX values and they all fit within a ~i' \times j'~ grid.

So, we can multiply ~dp[k-1][i'][j']~ by the number of ways to insert ~s[k-1], s[k-1]+1, \dots, s[k]-1~ into a surrounding ~i \times j~ grid, and sum over all valid ~i'~ and ~j'~ to compute ~dp[k][i][j]~.

Now, let us compute the ways to insert just ~s[k-1]~.

If ~i' < i~ and ~j' < j~, there are ~4~ ways, since ~s[k-1]~ must be placed at one of the four "corners" to be able to expand the minimal rectangle in both dimensions.

If ~i' = i~ and ~j' < j~, there are ~2i~ ways, since ~s[k-1]~ must be placed strictly to the left/right of all previously inserted values, while its row can be arbitrary among the existing rows.

If ~i' < i~ and ~j' = j~, there are ~2j~ ways, since ~s[k-1]~ must be placed strictly above/below all previously inserted values, while its column can be arbitrary among the existing columns.

Finally, after inserting ~s[k-1]~, we must insert ~s[k-1]+1, s[k-1]+2, \dots, s[k]-1~. There are

$$\displaystyle (ij-s[k-1]-1) \times (ij-s[k-1]-2) \times \dots \times (ij-s[k]+1) = \prod_{x=ij-s[k]+1}^{ij-s[k-1]-1} x$$

ways to do this because each value can fill in the remaining spots in the ~i \times j~ rectangle one by one, which is counted via a product of consecutive integers (the number of remaining spots decreases by one each time.

Overall,

$$\displaystyle dp[k][i][j] = \left(4\left(\sum_{i' < i, j' < j}dp[k-1][i'][j'] \right) + 2i\left(\sum_{j'<j}dp[k-1][i][j']\right) + 2j\left(\sum_{i'<i}dp[k-1][i'][j]\right) \right) \times \prod_{x=ij-s[k]+1}^{ij-s[k-1]-1} x$$

The sums can be optimized with prefix sums, and the product can be computed using preprocessed factorials and modular inverse.

The answer can be found in ~dp[|S|-1][N][M]~, where ~S~ is the set of achievable MEX values.

Time Complexity: ~\mathcal{O}(NM(N+M))~

Bonus

Author Commentary

Average Codeforces problem lol

Reference Solution

https://dmoj.ca/src/7439834