Distinct Initial Matrices

For a A * B matrix of all distinct numbers from 1 to A * B, we first sort each column and then concatenate all columns in increasing order of indices to form an array of size A * B. Columns are numbered in increasing order from left to right.

For example, if matrix is

[1 5 6]
[3 2 4]

We first sort all columns to get

[1 2 4]
[3 5 6]

Now, we concatenate columns in increasing order of indices to get an array

[1, 3, 2, 5, 4, 6]

Given this final array, you have to count how many distinct initial matrices are possible. Return the required answer modulo 109+7.

Two matrices are distinct if:
- Either their dimensions are different.
- Or if any of the corresponding row in two matrices are different.

Example:

If input array is [1, 3, 2, 4], distinct initial matrices possible are:

[1 3 2 4]
-----------------------
[1 2]
[3 4]
-----------------------
[1 4]
[3 2]
-----------------------
[3 2]
[1 4]
-----------------------
[3 4]
[1 2]
-----------------------

that is, a total of 5 matrices.
Interview Code Editor
155 successful submissions.
Click here to jump start your coding interview preparation