想定解と少し異なる方法を解説します。

まず、\(M\) が 2 冪の場合が解ければよいです。(\(M\) が 2 冪でない場合は 各行の先頭に \(\mathrm{pow}(2, \mathrm{ceil}(\log M)) - M\) 個の \(0\) を追加して問題を解いて大丈夫です。)

全てを mod 2 の世界で考えます。入力は \(N\) 個の mod 2 係数の行ベクトルとみなします。また、\(v_i\) \((0 \leq i \lt M)\) を次のように定義します。

• \(v_i\) : 長さ \(M\) の行ベクトルであって \(i \text{ AND } j = j\) である \(j\) について第 \(j\) 成分が \(1\) であるベクトル

さて、例えば \(M=8\) の場合, \(v_7\) からスタートして操作を行うとベクトルは次の挙動を示します。

11111111 = v_7
10101010 = v_6
11001100 = v_5
10001000 = v_4
11110000 = v_3
10100000 = v_2
11000000 = v_1
10000000 = v_0
11111111 = v_7
10101010 = v_6
...

このように 1 回操作するごとに \(v\) の添え字が \(1\) 減る仕組みになります。(\(v_{-1} = v_{M - 1}\) とします) \(M\) が一般の 2 冪の場合でもこの性質が成り立つことが二項係数 mod 2 の性質から容易に確認できます。

一般のベクトルにこの性質を生かすことを考えます。 一般のベクトル \(w\) を \(v_{\ast}\) の線形結合 \(w = a_0 v_0 + a_1 v_1 + \dots + a_{M-1} v_{M-1}\) として表したときの (このとき \(a\) は一意に定まります) 係数列 \((a_0, a_1, \dots, a_{M-1})\) を用いて \(w\) を表現することにします。 線形性を考えると、\(w\) に \(1\) 回操作した時、\(w\) は \(a_1 v_0 + a_2 v_1 + \dots + a_0 v_{M-1}\) に変化します。 よって係数列は \((a_1, a_2, \dots, a_0)\) に変化、すなわち幅 1 だけ left rotate shift したものになります。 よって、\(w\) を\(v_{\ast}\) の線形結合の係数列 \(a\) を用いて表現することで、操作を rotate shift という比較的扱いやすい概念で表現できるということがわかりました。

ベクトル \(w\) を \(v_{\ast}\) の線形結合で表す方法を求めることは subset メビウス変換で \(\mathrm{O}(M \log M)\) で出来ます。 全ての入力を \(v_{\ast}\) の線形結合に変換したあとは、おおよそ次のような問題を解けばよいです。

長さ \(M\) のベクトル \(A_1, A_2, \dots, A_N\) が与えられる。
\(f(i, j)\) を「\(A_i\) を幅 1 の left rotate shift によって \(A_j\) に一致させるのに必要な shift の最小回数 (不可能な場合は \(0\)) 」と定義する。
\(\left(\sum_{i=1}^N \sum_{j=i}^N f(i,j) \right) \bmod{998244353}\) を求めよ。

言い換え後の問題は Z-algorithm, suffix array, segtree を用いて \(\mathrm{O}(NM \log M)\) 程度で解けます。(この部分は ABC クラスの考察で処理できるので詳細は割愛します。)よって問題を解くことが出来ました。