SOLVE
LATER
Charlie has a grid G with N rows and M columns. The rows are numbered 0 through \(N-1\) from top to bottom. The columns are numbered 0 through \(M-1\) from left to right.
Each cell of the grid G contains a positive integer in the range \([1, N\times M]\). Each of these numbers occurs in the grid exactly once.
In Charlie's eyes, the most beautiful of all grids is the sorted grid \(G_S\) : A grid of size \(N \times M\) whose list of elements in row major order is the ordered sequence \([1,2,3,...,N\times M]\). For example with \(N=2\) and \(M=3\), \( G_S = \begin{bmatrix} 1 & 2 & 3\newline 4 & 5 & 6 \end{bmatrix}\)
Denote \(F(G) \) = Number of pairs \((i,j)\) such that \(G[i][j] = G_S[i][j], 0 ≤ i < N, 0 ≤ j < M\)
For example:
\( F\Bigg(\begin{bmatrix}
1 & 2 & 3\newline
4 & 5 & 6
\end{bmatrix}\Bigg) = 6, \)
\( F\Bigg(\begin{bmatrix}
3 & 2 & 1\newline
5 & 4 & 6
\end{bmatrix}\Bigg) = 2\)
Charlie can also modify the grid by applying the following two operations any number of times:
Let S denote the set of distinct grids G that Charlie can generate from the input grid G.
You need to print the sum \(\displaystyle \sum\limits_{G'\in S} F(G')^2\)
Since the result can be large, print it modulo \(10^9+7\)
The first line will contain two integers \(N, M\).
The next N lines will contain M integers each. The \(i^{th}\) line describes the numbers in the \(i^{th}\) row of G.
The input grid numbers are guaranteed to be a permutation of \([1,2,3,..,N\times M]\).
Output the desired sum modulo \(10^9+7\) in a single line.
There are 100 files. Your solution will get a score equal to the number of files you pass. Some files may have different bounds, as detailed below.
For all subtasks:
\(2 ≤ N, M\)
Subtask 1 (36 files):
\(N, M ≤ 3\)
Subtask 2 (27 files):
\(N, M ≤ 7\)
Subtask 3 (18 files):
\(N, M ≤ 50\)
Subtask 4 (9 files):
\(N, M ≤ 300\)
Subtask 5 (10 files):
\(N, M ≤ 1500 \)
There are 12 configurations we can reach
\( F\Bigg(\begin{bmatrix}
2 & 5 & 1\newline
6 & 3 & 4
\end{bmatrix}\Bigg) = 0, \)
\( F\Bigg(\begin{bmatrix}
2 & 1 & 5\newline
6 & 4 & 3
\end{bmatrix}\Bigg) = 0, \)
\( F\Bigg(\begin{bmatrix}
5 & 2 & 1\newline
3 & 6 & 4
\end{bmatrix}\Bigg) = 1, \)
\( F\Bigg(\begin{bmatrix}
5 & 1 & 2\newline
3 & 4 & 6
\end{bmatrix}\Bigg) = 1, \)
\( F\Bigg(\begin{bmatrix} 1 & 2 & 5\newline 4 & 6 & 3 \end{bmatrix}\Bigg) = 3, \) \( F\Bigg(\begin{bmatrix} 1 & 5 & 2\newline 4 & 3 & 6 \end{bmatrix}\Bigg) = 3, \) \( F\Bigg(\begin{bmatrix} 6 & 3 & 4\newline 2 & 5 & 1 \end{bmatrix}\Bigg) = 1, \) \( F\Bigg(\begin{bmatrix} 6 & 4 & 3\newline 2 & 1 & 5 \end{bmatrix}\Bigg) = 1, \)
\( F\Bigg(\begin{bmatrix} 3 & 6 & 4\newline 5 & 2 & 1 \end{bmatrix}\Bigg) = 0, \) \( F\Bigg(\begin{bmatrix} 3 & 4 & 6\newline 5 & 1 & 2 \end{bmatrix}\Bigg) = 0, \) \( F\Bigg(\begin{bmatrix} 4 & 6 & 3\newline 1 & 2 & 5 \end{bmatrix}\Bigg) = 1, \) \( F\Bigg(\begin{bmatrix} 4 & 3 & 6\newline 1 & 5 & 2 \end{bmatrix}\Bigg) = 1\)
The sum of \(F(G)^2\) is equal to \(1^2+1^2+3^2+3^2+1^2+1^2+1^2+1^2=24\)