We consider a dynamic programming (DP) approach.

The value \(\mathrm{dp}[h][w][s]\) is defined as “the number of \(h \times w\) matrices \(A\) that satisfy the conditions of the problem statement, where no duplicate row or column exists, and at least one element of \(1\) exists in the first row and the first column, and the values in the final column (column \(w\)) are \(s = (A_{1, w}, \dots, A_{h, w})\), modulo \(M\)”.

The transition from \(\mathrm{dp}[h][w][s]\) to \(\mathrm{dp}[*][w + 1][s_{\mathrm{next}}]\) involves considering the position where a tie-break occurs between \(s\) and \(s_{\mathrm{next}}\). For the digits at or below the tie-break position, each digit of \(1\) in \(s\) may correspond to two digits in \(s_{\mathrm{next}}\).

For example, when adding one column to the right of the \(2\)-column matrix

\[ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \]

to transition to a \(3\)-column matrix, not only the simple transition of adding one column

\[ \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \]

but also transitions like duplicating the second row of the original matrix

\[ \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{pmatrix} \]

and transitions where a tie-break occurs in a row above the previous first row

\[ \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & a \\ 1 & 0 & b \end{pmatrix} \]

(where \(a\) and \(b\) can each be either “0”, “1”, or “the row is duplicated with each row containing 0 and 1”) need to be considered.

The algorithm in \(O(2^H W)\) can be achieved by efficiently implementing the processes that collapse the information of digits below the tie-break position and branch the digits below the tie-break position into “0”, “0 and 1”, or “1”.