公式解説に記載されている通り、この問題は行列の累乗を計算する問題と考えることができます。
しかし、ナイーブに考えると、行列の次数が\(49\) となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

行列の次元を小さくする方法

\(28\)次元の行列

gksato さんの解説ですでに言及されている通り、少し工夫することで行列の次元を\(28\) に減らすことができます。
下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。
提出例

\(13\)次元の行列（ただし行列の個数は\(6\)つ）

NPCAPC とnpcapc のそれぞれを別々に考慮すると、行列の次元はこれらの文字列の長さの積のオーダーになってしまいます。
そこで、この\(2\)つの文字列を組み合わせた文字列を\(1\)つ固定することで、行列の次元を\(13\)にする、つまり文字列の長さの和のオーダーにすることを考えます。
\(N=12\) のときの答えが\(924\) であることから、このような文字列が\(924\) 個あることがわかりますが、それらを一つ一つ処理していたら寧ろ効率が悪くなるため、同じ行列になるような文字列をまとめることで、\(6\) つのグループに分けます。
具体的には、\(0 \le k < 6\) を満たす整数\(k\) それぞれについて、対角成分に\(50\) が\(6+k\) 個、\(51\) が\(6-k\) 個、\(52\) が\(1\) 個並び、そこから一つずれて\(1\) が斜めに並ぶような行列になるグループが考えられます。

これにより行列の次数が上と比較しても半分以下となるため、行列の積は単純に考えると\(8\) 倍効率化されます。 よって、行列が\(6\) つに増えても全体では\(\frac{3}{4}\) 程度の計算で答えが求められる見込みです。
下記の提出例を見る限り、上の方法と比較して、実際に実行時間が短くなっています。
提出例

行列の累乗の一般的な計算方法

対角化

対角行列の積は簡単に求められるため、行列の対角化は行列の累乗を計算したいときの常套手段の一つと考えられます。
ただし、行列の対角化は任意の正方行列に対して可能というわけではなく、今回の問題に対しても上で考えた行列を対角化することはできません。
そのため、今回の問題では対角化による行列の累乗の計算を活用することは難しいと思われます。

ジョルダン標準形

ジョルダン標準形とは、行列の対角化を一般化したものであり、これも累乗が計算しやすい形となっています。
また、対角化とは違い、より広い範囲の行列に適用できる技術であるため、今回の問題にもそのまま活用できます。
下記の提出で、上で述べた次数\(13\) の行列の場合について、実際にジョルダン標準形を使って答えを求めてみました。
提出例

ちなみに今回の問題でジョルダン標準形が使えた理由としては、上で考えた行列が三角行列であったことが理由として大きいと考えます。
三角行列であることによって、計算を別途しなくとも固有値がわかり、固有値が\(\mathbb{F}_{998244353}\) の元であることが明確であるからです。
有限体は代数的閉体ではないため、一般の行列については固有値が\(\mathbb{F}_{998244353}\) の元にならないこともあります。
また、固有値が\(\mathbb{F}_{998244353}\) の元だったとしても、固有多項式を現実的な時間で解けるとは限りません。
今回の場合は三角行列であったため固有値が明白であり、そこからの計算は四則演算だけであるため、\(\mathbb{F}_{998244353}\) の中で計算できました。