All Tracks Math Problem

Grid Scramble
Tag(s):

Math, Medium, approved

Problem
Editorial
Analytics

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:

  • Swap any two rows
  • Swap any two columns

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$$

Input Format:

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 Format:

Output the desired sum modulo $$10^9+7$$ in a single line.

Constraints

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 $$

SAMPLE INPUT
2 3
2 5 1
6 3 4
SAMPLE OUTPUT
24
Explanation

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$$

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

December Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications