\(\mathrm{dp}[h][w][s]\) を「問題文の条件を満たす \(h\) 行 \(w\) 列の行列 \(A\) であって、全ての要素が共通の行や共通の列が存在せず、かつ \(1\) 行目と \(1\) 列目に \(1\) の要素が存在し、最終列（ \(w\) 列目）の値たちが \(s = (A_{1, w}, \dots, A_{h, w})\) であるものの個数（を \(M\) で割った余り）」とおいて、DP を回すことを考えます。

\(\mathrm{dp}[h][w][s]\) から \(\mathrm{dp}[*][w + 1][s_{\mathrm{next}}]\) への遷移は、\(s\) と \(s_{\mathrm{next}}\) のタイブレークが起きる位置に注目して場合分けします。タイブレークが起きる桁やそれより下の桁では、\(s\) の \(1\) 桁に対して \(s_{\mathrm{next}}\) の \(2\) 桁が対応する可能性があります。例えば、

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

という \(2\) 列の行列の右に \(1\) 列追加して \(3\) 列の行列に遷移する際、単に \(1\) 列増える

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

という遷移だけでなく、もとの行列の \(2\) 行目を複製した

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

という遷移や、これまでの \(1\) 行目より上の行でタイブレークが起きる

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

のような遷移（ \(a\) や \(b\) にはそれぞれ「\(0\)」 or 「\(1\)」 or 「行が \(2\) 行に複製され、各行に \(0\) と \(1\) が入る」のいずれかが入る）なども考える必要があります。

この DP の実装にあたって、タイブレークが起きる桁より下位の桁の情報を潰していく処理や、タイブレークが起きる桁より下位の桁を 「\(0\)」 / 「\(0\) と \(1\)」 / 「\(1\)」 の \(3\) 通りに分岐させる処理を効率的に実装することで、 \(O(2^H W)\) で動作するアルゴリズムが得られます。